알고리즘 공부 - 최소비용신장트리

안녕하세요. yeTi입니다.
오늘은 알고리즘 공부 중 최소비용신장트리(Minimum Spanning Tree)에 대해 학습한 내용을 공유하려고 합니다.
강의 : 권오흠 교수님의 2015 봄학기 알고리즘

개요

최소비용신장트리는 무방향 가중치 그래프에서 모든 노드를 이었을 때 가중치가 가장 적은 엣지들의 부분집합을 찾는 방식입니다.

이 때, MST(Minimum Spanning Tree) 는 유일하지 않기 때문에 선별한 엣지들을 많은 MST들 중 일부인 부분집합 이라는 표현을 한다.

공학적으로는 계층적 구조의 연결을 트리(rooted tree)라고 인식하지만 수학적으로는 싸이클이 없는 연결된(connected) 무방향 그래프를 트리라고 합니다. 게다가 MST 문제에서 싸이클이라는 것은 중복 경로라는 의미로 해석할 수 있고 중복 경로가 있다는 것은 최소비용이 아니기 때문에 MST 문제의 답은 항상 트리가 됩니다.

MST는 network design의 기초 알고리즘으로 사용합니다. 대표적으로 Kruskal's algorithm과 Prim's algorithm이 있습니다.

여기서는 먼저 두 알고리즘의 공통 로직인 Generic algorithm을 다룹니다.

Generic algorithm

아이디어는 간단합니다.

어떤 MST의 부분 집합인 A에 대해서 AU{(u, v)} 도 MST의 부분 집합이 될 경우 에지(u, v)는 A에 대해서 안전하다(safe)고 합니다.

따라서 집합 A에 대해 안전한 엣지 하나를 찾은 후 A에 더해 나가는 것이 기본 아이디어 입니다.

그렇다면 안전한 엣지는 어떻게 찾을 수 있을까요?

먼저 용어를 정의해야 합니다. 컷(cut) (S, V-S), cross한다, 존중한다(respect)

• 그래프의 노드들을 두 개의 집합 S와 V-S로 분할한 것을 컷(cut) (S, V-S)라고 부릅니다.
• 엣지 (u, v)에 대해서 u∈S이고 v∈V-S일 때 엣지 (u, v)는 컷(cut) (S, V-S)를 cross한다로 말합니다.
• 엣지들의 부분 집합 A에 속한 어떤 엣지이고 컷(cut) (S, V-S)를 cross하지 않을 때 컷(cut) (S, V-S)는 A를 존중한다(respect)고 말합니다.

안전한 엣지는 집합 A가 어떤 MST의 부분 집합이고, (S, V-S)는 A를 존중하는 컷이라고 했을 때, 이 컷을 cross하는 엣지들 중 가장 가중치가 작은 엣지 (u, v) 입니다.

Kruskal's algorithm

Kruskal's algorithm의 아이디어는 간단합니다.

그래프의 엣지들을 가중치를 기준으로 오름차순 정렬을 한 이후에 공집합 A에 가장 작은 엣지들을 하나씩 추가하는 방법입니다. 이 때, 추가하려는 엣지가 싸이클을 만들지 않도록 해주면 됩니다.

어떻게 이러한 방식이 MST를 달성할 수 있을까요?

Generic algorithm에서 MST를 만드는 방식은 집합 A에 대해 안전한 엣지 하나를 찾은 후 A에 더해 나가는 것이라고 했습니다.

여기서 안전한 엣지에 대해 kruskal's algorithm이 보장하는 방법은 싸이클을 만들지 않는 최소 가중치를 가진 엣지를 찾는 것입니다. 싸이클에 대해 판단하는 방식은 주어진 그래프의 모든 노드를 개별 부분 집합으로 간주하고 최소 가중치를 가진 엣지의 두 노드가 동일한 집합내에 존재하지 않는다면 해당 엣지는 싸이클을 만들지 않는다고 판단합니다.

조금 더 구체적으로 접근해 보겠습니다.

그래프의 각각의 노드들을 유일한 원소로 가지는 집합은 어떻게 만들 수 있을까요? 이는 서로소인 집합들을 어떻게 표현할 것인가에 대한 문제로 볼 수 있습니다.

서로소인 집합들은 상향식 트리를 사용하여 1차원 배열로 모든 집합을 표현할 수 있습니다.

두 노드가 동일한 집합내에 존재하는지는 어떻게 찾을 수 있을까요?

이는 1차원 배열에서 각 원소들이 가지는 루트를 찾아서 동일한 루트를 가진다면 동일한 집합으로 볼 수 있습니다. 이 때 시간복잡도는 O(h)를 가지는데 최악의 경우에는 O(n)을 가집니다.

마지막으로 엣지를 어떻게 합칠까요?

서로다른 두 집합에서 한 집한의 루트를 다른 집합의 루트의 자식으로 만들면 됩니다. 이 때 집합을 합지는 시간복잡도는 O(1)이지만 루트를 찾는 시간복잡도는 O(h)입니다.

이렇게 계산한 시간복잡도로 나온 Kruskal's algorithm의 시간복잡도는 O(mn)입니다. 왜냐하면 각 step의 시간복잡도는 다음과 같기 때문입니다.

• Initialize A: O(n)
• Make set : O(n)
• Sort E : O(mlogm)
• Find and Union : O(mn)

현 상황에서 Find and Union step을 개선하여 시간복잡도를 개선할 수 있습니다.

Weighted Union은 union시 노드의 갯수가 많은 트리의 부트리로 갯수가 적은 트리를 union 하는 방식입니다. 이렇게 함으로써 트리의 높이는 logn 으로 줄일 수 있어 특정 원소의 루트는 찾는 시간복잡도를 O(n)에서 O(logn)으로 개선할 수 있습니다.

또한 path compression을 통하여 path를 탐색하는 step을 부모에서 조부모로 변경함으로써 트리의 높이를 반으로 줄여주는 효과가 있습니다.

결론적으로 WUPC(Weighted Union with Path Compression)를 하게 되면 O(N+Mlog*N)의 시간복잡도를 가지게 됩니다. 여기서 log*N의 값은 매우 크기 때문에 거의 선형시간 알고리즘이지만 현실적인 경우에는 O(1)의 시간복잡도를 가지게 됩니다.

따라서 기존 Find and Union : O(mn)를 O(1)으로 시간복잡도를 개선할 수 있게 되고 Kruskal's algorithm의 최종 시간복잡도는 O(mlogm)을 가집니다.

Prim's algorithm

Prim's algorithm의 아이디어는 간단합니다.

임의의 한 노드를 기준으로 인접한 엣지 중 가중치가 가장 작은 엣지에 있는 노드를 하나씩 추가하는 방법입니다. 이 때, 이미 트리에 포함된 노드에서 포함되지 않은 노드를 연결하는 엣지들 중 선택해야 합니다.

어떻게 이러한 방식이 MST를 달성할 수 있을까요?

Generic algorithm에서 MST를 만드는 방식은 집합 A에 대해 안전한 엣지 하나를 찾은 후 A에 더해 나가는 것이라고 했습니다.

여기서 안전한 엣지에 대해 Prim's algorithm이 보장하는 방법은 임의의 노드를 기준으로 생성된 트리가 어떤 MST의 부분 집합이고, (S, V-S)는 해당 트리를 존중하는 컷이라고 했을 때, 이 컷을 cross하는 엣지들 중 가장 가중치가 작은 엣지를 선택하는 것입니다.

이러한 prim's algorithm 의 극단적인 시간복잡도는 O(n^3)입니다. 왜냐하면 집합 (S, V-S)가 각각 n/2개의 노드를 가지고 있다고 가정했을 때 최소 가중치의 엣지를 찾기위한 경우의 수는 (n/2)^2이고 이러한 연산을 n-1 개의 엣지만큼 해야하기 때문입니다.

이러한 비효율을 해결하는 것이 prim's algorithm을 구현하기 위한 포인트입니다.

개선을 위한 아이디어는 후보 노드가 가진 엣지들 중 최소 가중치를 가진 엣지의 정보를 기억하는 것입니다.

바로 MST에 포함되지 않은 노드 v에 대해서 MST에 속한 노드와 자신을 연결하는 엣지들 중 가중치가 최소한인 엣지 (u, v)의 가중치인 key(v), 해당 엣지 (u, v) 끝점인 u를 표현하는 π(v) 입니다.

key(v)와 π(v)를 활용하면 최소 가중치의 엣지를 찾기 위해서 모든 대상 엣지를 탐색하는것이 아니고 key(v)가 최소인 엣지를 탐색하면 되기 때문에 O(n) 시간복잡도를 가질 수 있습니다.

또한 key(v)의 갱신의 관점에서도 연결한 키와 인접한 엣지들에 대해서만 갱신하면 되기 때문에 최대 O(n) 시간복잡도를 가집니다.

따라서 최소 가중치의 엣지를 찾는데 O(n^3)에서 O(n^2)으로 시간복잡도를 줄일 수 있습니다.

아직 시간복잡도의 개선의 여지가 있습니다.

key(v)가 최소인 엣지를 탐색할 때 최소 우선순위 큐를 사용하는 것입니다. 최소 우선순위 큐는 Min Heap으로 시간복잡도 O(logn)으로 구현가능합니다. 또한 인접 리스트 자료구조를 활용하면 인접 노드를 찾을 때 O(degree(v)) 시간복잡도를 가질 수 있습니다.

따라서 최종적으로 O(mlogn)의 시간복잡도를 가지므로 Kruskal's algorithm, O(mlogm)보다 좋은 성능을 가졌다고 볼 수 있습니다. (왜냐하면 m(엣지의 총 수)보다 n(노드의 수)의 갯수가 적기 때문입니다.)

• n회 최소 엣지 탐색 : O(nlogn)
• m회 key 재정렬 : O(mlogn)
• 따라서 O(nlogn + mlogn) : O(mlogn)

추가적으로 최소 우선순위 큐를 사용하지 않고 Fibonacci Heap을 사용할 경우 O(m+nlogn)의 시간복잡도를 가질 수 있습니다.

관련 강의

• [알고리즘] 제15-1강 최소비용신장트리(minimum spanning tree)
• [알고리즘] 제15-2강 최소비용신장트리(minimum spanning tree) (계속)
• [알고리즘] 제15-3강 최소비용신장트리(minimum spanning tree) (계속)
• [알고리즘] 제15-4강 최소비용신장트리(minimum spanning tree) (계속)

관련 글

• 알고리즘 공부 - 그래프
• 알고리즘 공부 - 해싱
• 알고리즘 공부의 필요성
• 알고리즘 공부 - 트리
• 알고리즘 공부 - sort
• 알고리즘 공부 - recursion
• 알고리즘을 공부해야하는 이유