Graph Algorithm   그래프 알고리즘

(2023-11-03)

1. 그래프 알고리즘을 크게 구분하면,그래프 내 모든 정점을 순회하는 방법   ☞ (2.항) 참조
  ㅇ 작업 사이에 특정 의존(순서)관계가 있을 때 이를 정렬시키는 방법   ☞ (3.항) 참조
  ㅇ 루프가 없는 그래프(신장 트리)를 생성시키는 방법   ☞ (4.항) 참조
  ㅇ 최소 신장 트리를 작성하는 방법   ☞ (5.항) 참조
  ㅇ 그래프 상에서 최단 경로를 탐색하는 방법   ☞ (6.항) 참조


2. 그래프 순회 방법 (Graph Traversal), 그래프 탐색/그래프 검색 방법 (Graph Search)그래프 순회
     - 모든 정점을 빠짐 없이, 중복 없이, 방문하는 것

  ㅇ 그래프 탐색
     - 그래프 순회를 통해 모든 정점들을 훑으는 도중에, 원하는 정점을 찾는 것 

  ㅇ 주로,
     - 모든 정점을 한번씩 만 방문하거나, 
     - 모든 정점을 한번씩 만 방문하면서 목표 정점을 찾아가거나,
     - 또한, 특정 정점에서 다른 정점으로 갈수 있는지, 서로 연결되었는지 등을
     - 확인하는데에 사용 

  ㅇ (대표적인 例 둘)  
     - 깊이 우선 탐색 (Depth First Search, DFS)
     - 너비 우선 탐색 (Breadth First Serach, BFS)


3. 작업 순서의 정렬 방법

  ㅇ 작업 사이에 특정한 의존 관계(선행 의무)가 있는 경우에 순서화시키는 정렬 방법을 찾음

  ㅇ (대표적인 例) : 위상 정렬 (Topological Ordering) 알고리즘
     - 방향성 비순환 그래프에서, 1 이상의 선형적 순서를(1 이상 방법으로 정렬하여) 생성해 냄


4. 생성 트리/신장 트리의 작성 방법 (Spanning Tree)

  ㅇ 여기서, 생성 트리/신장 트리 이란?
     - 루프가 없는 그래프를 말함

  ㅇ 그래프의 모든 정점을 한번씩 만 방문하며 (특히, 루프없이), 
     - 결국, 모두를 포함하되 루프는 없게되는, 부분 그래프(트리)를 작성하는 방법

  ㅇ (방법)
     - 연결그래프에서 그래프 순회(Graph Traversal)를 하면,
     - n-1개 간선(링크)를 이동하면서 모든 정점을 방문하게 되므로,
     - 결국 이것이 신장트리(생성트리)를 만들게 됨


5. 최소 생성트리/신장트리 작성 알고리즘 (Minimum Spanning Tree)

  ㅇ 연결선에 부여된 가중치 합이 최소가 되도록 신장트리를 작성하는 알고리즘

  ㅇ (대표적인 例)
     - 쿠르스칼 알고리즘 (Kruskal Algorithm)
        . 루프를 만들지 않으면서 최소 가중치 연결선을 하나씩 추가하며 최소 신장트리 작성
     - 프림 알고리즘 (Prim Algorithm)
        . 임의 정점부터 시작하며 연결된 연결선 중 최소 가중치를 갖는 연결선을 추가하고,
        . 루프를 만들지 않으면서 점차 선택된 정점들에 부속된 연결선들 중
          최소 가중치 연결선을 추가하며 최소 신장트리 작성               


6. 최단 경로 탐색 알고리즘 (Shortest Path Algorithm)

  ㅇ 두 정점 간에, 가중치 합이 최소가 되는 경로를 찾는 알고리즘최단 경로 문제의 종류
     - 단일 출발지,단일 목적지 최단 경로 문제 
     - 단일 출발지 최단경로 문제
     - 단일 도착지 최단경로 문제
     - 모든 쌍 최단경로 문제

  ㅇ (대표적인 例)
     - Dijkstra 알고리즘  :  (단일 출발지 최단경로 문제)
        . 단일 시작점으로부터 모든 정점까지, 
        . 각 정점에 대해 최단 경로를 하나씩 결정하면서,
        . 점차 그래프 전체를 탐색해나감
     - 벨만 포드 알고리즘  :  (단일 출발지 최단경로 문제)
        . 모든 간선에 대해 (모든 정점 쌍 간에), 가중치를 계산, 갱신해가며,
        . 가중치가 변경되지 않을 때까지 처리를 반복해나감
     - 플로이드 알고리즘 등  :  (모든 쌍 최단경로 문제) 
        . 우선 그래프를 표현하는 인접 행렬을 구해 놓고,
        . 두 정점 간에 가능한 모든 경로 비용들을 비교하여 최단 거리를 구하며, 이를 저장하고,
        . 전체 두 정점 간에 이를 적용하며, 최소 비용 테이블을 구함

그래프 알고리즘
   1. 그래프 알고리즘   2. 그래프 순회 (DFS,BFS)   3. 깊이 우선 탐색 (DFS)   4. 너비 우선 탐색 (BFS)   5. 위상 정렬   6. 최소 신장 트리   7. 최단 경로   8. 다익스트라 알고리즘   9. 플로이드 알고리즘  
알고리즘 종류
   1. 알고리즘 분류   2. 그래프 알고리즘   3. 몬테칼로 알고리즘  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"