이번 장에서 배우는 가중 그래프(Weighted Graph)는 정점(Vertex)를 연결하는 간선(Edge)에 가중치를 부여한 것입니다.
예를 들어 정점을 도시라고 생각하고, 간선은 도시를 연결하는 도로라고 한다면, 간선에 매겨진 가중치는 이동하는데 걸리는 비용(시간, 통행료, 연료비 등)이라고 모델링할 수 있습니다.
이런 모델링이 자연스럽기 때문에 가중 그래프의 예로는 두 정점 간의 최소 비용 경로(최단 경로)를 찾는 것이 주요 문제가 됩니다.
자동차의 최단 경로를 안내하는 내비게이션도 도로를 가중 그래프로 모델링하고 그 안에서 최소 비용 경로를 찾는 것입니다.
이번 장에서 가중 그래프를 프로그램으로 표현하는 법, 그리고 최소 비용 신장 트리를 찾기 위한 Kruskal 알고리즘과 최단 경로를 찾기 위한 Dijkstra 알고리즘에 대해 알아볼 것입니다.
강의 자료
강의 동영상
21.0 가중 그래프 - 시작 : 가중 그래프는 간선에 가중치를 부여한 그래프입니다. 이를 이용하여 여러가지 최단 경로 관련 문제를 해결할 수 있습니다. 이번장에서 배울 내용들을 훑어 봅니다.
21.1 가중 그래프의 개요 : 도시와 도로망을 예로 들어 가중 그래프의 개념을 살펴 봅니다. 그리고 가중 그래프를 프로그램에서 어떻게 표현하는지도 살펴 봅니다.
21.2 최소 비용 신장트리와 우선순위 탐색 : 그래프의 모든 정점을 지나는 트리 중에서 간선 비용의 합이 최소인 트리를 최소 비용 신장 트리라고 합니다. 이를 이용하여 최소의 비용으로 네트워크를 구성하는 문제 등을 해결할 수 있습니다. 그리고 이후 논의에서 사용될 도구로 우선순위 탐색에 대한 개념과 구현을 알아 봅니다.
21.3 집합 연산 : 다음에 다룰 Kruskal 알고리즘을 구현하려면 우선 순위 탐색과 집합 연산이 필요합니다. 집합은 순서를 따지지 않는 요소들을 모아 놓은 것으로 방향 그래프로 표현될 수 있습니다. 집합의 표현과 효율적인 Union 연산을 구현해 봅니다.
21.4 Kruskal 알고리즘 : 최소 비용 신장 트리를 구하기 위한 대표적인 방법인 Kruskal 알고리즘의 개념과 구현을 알아 봅니다. 앞서 공부했던 우선 순위 탐색과 집합의 개념을 이용하면 매우 단순한 알고리즘으로 정리됩니다.
21.5 최단 경로 찾기 - 우선순위 탐색 : 최단 경로 문제를 정의하고 그 문제를 해결하기 위해 우선 순위 탐색을 구현해 봅니다. 앞서 배운 최소 비용 신장 트리의 우선순위는 가중치 자체였지만, 최단 경로를 찾기 위한 탐색은 경로를 이루는 간선 가중치의 누적값이 된다는 차이가 있습니다.
21.6 최단 경로 찾기 - Dijkstra 알고리즘 : 아주 간단한 논리 전개로 최단 경로 알고리즘을 풀 수 있는 Dijkstra 알고리즘에 대해 배우고 구현해 봅니다. 최단 경로 문제를 푸는데 있어 기본이 되는 매우 중요한 알고리즘입니다.
21.9 가중 그래프 - 결론 : 간선에 비용이 있는 가중 그래프로 해결하고자 하는 문제는 모두 최소 비용의 경로를 찾는 것입니다. 이를 해결하기 위한 몇몇 알고리즘 들을 살펴 보았습니다. 하지만 이 문제는 현실 세계에서 매우 중요하기 때문에, 더 발전된 연구들이 있습니다.
관련글 |
- C++로 배우는 알고리즘
- 20장 : 그래프의 기본 (Graph Basics)
- 22장 : 방향 그래프 (Directed Graph)
댓글 없음:
댓글 쓰기