신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다.
최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다.
이러한 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 선택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 크루스칼(Kruskal) 알고리즘을 알아보도록 하겠습니다.
프림 알고리즘 : https://withhamit.tistory.com/321
크루스칼 알고리즘은 일단,
간선을 비용을 기준으로 오름차순 정렬한 뒤, 작은 비용의 간선부터 연결하여 트리를 완성해갑니다.
간선을 연결할 때, 사이클(cycle)이 발생하면 해당 간선을 연결하지 않습니다.
이를 모든 간선을 탐색할 때 까지 반복합니다. (MST의 간선의 수는 정점-1이므로 간선의 개수를 세어가면서 정점-1개를 연결했을 때 종료한다면 더 빠른 알고리즘을 만들 수 있습니다.)
이제 [그림 1]과 같은 그래프의 MST를 크루스칼 알고리즘을 이용하여 만들어보겠습니다.
왼쪽에 있는 표는 간선 정보로 정점 a, b를 연결하는 간선이 있고 이 간선 비용이 얼마인지를 나타냅니다. 표에 있는 모든 간선을 연결하면 오른쪽 그림과 같은 그래프가 됩니다.
우선 간선들을 비용을 기준으로 오름차순 정렬합니다.
이제 정렬된 간선 정보에서 작은 비용의 간선부터 그래프에 연결해줍니다.
(2, 3)을 연결합니다.
(4, 5)를 연결합니다.
(1,3)을 연결합니다.
(1,2)를 연결하려고 하는데 이 때, 만약 1과 2를 잇는 간선을 연결하면 오른쪽 그래프에서와 같이 정점 1, 2, 3 사이에 사이클이 발생합니다. 사이클이 발생한다는 것은 굳이 해당 간선을 연결하지 않아도 다른 간선을 이용하여 간선에 연결된 두 정점간에 이동할 수 있다는 뜻입니다. 따라서 필요없는 간선이므로 해당 간선은 연결하지 않고 다음 간선을 탐색합니다.
(3, 4)를 연결합니다.
(2, 4) 간선을 연결하려고 하는데 그러면 정점 2, 3, 4 사이에 사이클이 만들어지므로 해당 간선을 채택하지 않고 다음 간선을 탐색합니다.
(4, 6) 간선을 연결합니다.
(4, 6) 간선을 연결하면 현재 완성된 그래프에 간선의 개수가 5개 즉, 6(정점) - 1개가 연결되어 있으므로 MST를 이미 완성했다는 것을 알 수 있습니다. 따라서 여기서 종료해도 되지만 남은 간선을 탐색하는 경우도 마저 알아보겠습니다.
(5, 6) 간선을 연결하는 경우 정점 4, 5, 6 사이에 사이클이 발생하므로 채택하지 않고 다음 간선을 탐색합니다.
(3, 5) 간선을 연결하는 경우도 정점 3, 4, 5 사이에 사이클이 발생하므로 채택하지 않습니다.
모든 간선을 탐색하여 만들어진 MST 그래프는 위 그림과 같습니다.
해당 MST를 만드는 비용은 채택된 간선들의 합이므로 2+3+4+6+8 =23이 됩니다.
초반에 "간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재한다"는 이야기를 했는데, [그림 2]의 표를 보면 7번째 간선과 8번째 간선의 비용이 같은 것을 볼 수 있습니다.
왼쪽 그래프는 7번째 간선을 선택하였을 때 완성된 MST이고 오른쪽 그래프는 8번째 간선을 선택했을 때 완성된 MST입니다.
두 그래프 모두 최소 스패닝 트리의 조건을 만족하므로 둘 다 MST라고 할 수 있습니다.
구현 시 사이클이 발생하는 것을 판단하는 방법 중 하나는 유니온-파인드(Union-Find)를 이용하는 것입니다.
간선을 연결할 때 먼저 간선에 연결된 두 정점 a, b의 루트 노드를 Find 함수로 찾고
만약 찾은 두 루트 노드가 같다면이미 이동할 수 있는 경우, 즉 같은 연결 그래프로 묶여 있는 경우이므로 해당 간선을 연결한다면 사이클이 발생하므로 연결하지 않습니다.
찾은 루트 노드가 같지 않다면해당 간선을 연결하고 하나의 정점의 루트 노드를 다른 정점의 루트 노드로 갱신하는 Union 함수를 이용하여 두 정점이 속한 부분 그래프가 합쳐짐을 구현합니다.
MST를 이용하는 문제입니다.
네트워크 연결(1922) : https://www.acmicpc.net/problem/1922
소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/tip/%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC.cpp
fpdjsns/Algorithm
알고리즘 정리. Contribute to fpdjsns/Algorithm development by creating an account on GitHub.
github.com
참고 : http://terms.naver.com/entry.nhn?docId=837730&cid=42344&categoryId=42344
'알고리즘 이론' 카테고리의 다른 글
| 다이나믹 프로그래밍(Dynamic Programming) (0) | 2020.02.22 |
|---|---|
| KMP 알고리즘 (0) | 2020.02.09 |
| 프림 알고리즘(Prim's algorithm) (0) | 2020.02.06 |
| 세그먼트 트리(Segment Tree) (0) | 2020.02.02 |
| 트리 순회(전위 순회, 중위 순회, 후위 순회) (2) | 2019.10.04 |
댓글