Graph Algorithm   그래프 알고리즘

(2022-02-24)

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



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