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