[CS과목/자료구조] 11 그래프 2

교재: C언어로 쉽게 풀어쓴 자료구조 개정 3판 (2019, 천인국 외)

 

11.1 최소 비용 신장 트리

신장 트리

 신장 트리(spanning tree)란 그래프 내의 모든 정점들이 연결되어 있으며 사이클을 포함하지 않는 트리이다. 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 신장 트리는 그래프의 최소 연결 부분 그래프가 된다. 최소의 의미는 간선의 수가 가장 적다는 의미히다.

 

최소 비용 신장 트리

 최소 비용 신장 트리(MST: minimum spanning tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 이를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있다.

 

11.2 Kruskal의 MST 알고리즘

 Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. 탐욕적인 알고리즘에서 순간의 선택은 그 당시에는 최적이다. 하지만 전역적으로 최적이라는 보장이 없기에 검증해야 한다. 다행히 Kruskal의 알고리즘은 최적의 해답을 주는 것으로 증명되어 있다. Kruskal의 알고리즘은 먼저 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가한다. 만약 사이클을 형성하면 그 간선은 제외된다. Kruskal의 알고리즘은 최소 비용 신장 트리를 구하는 다른 알고리즘보다 간단해 보인다. 하지만 다음 간선을 이미 선택된 간선들의 집합에 추가할 때 사이클을 생성하는 지를 체크하여야 한다. 이 검사를 위한 알고리즘을 union-find 알고리즘이라 부른다.