최소 신장 트리(minimum spanning tree, MST)는 최소의 비용으로 주어진 그래프의 모든 정점을 연결하는 방법으로, 학부 자료구조 수업이나 알고리즘 수업에서 이를 찾는 문제를 분명 배우셨을 겁니다. 예전에 저도 자료구조 시간에 이 문제를 배웠던 기억이 있습니다. 당시 이 문제를 푸는 방법으로 크루스칼 알고리즘(Kruskal's algorithm)과 프림 알고리즘(Prim's algorithm)을 배웠습니다. 아마 이 두 알고리즘이 가장 유명한 방법이 아닐까 싶습니다.
그런데 최근 두 알고리즘과는 또 다른 알고리즘을 알게 되었습니다. 바로, 보루프카 알고리즘(Borůvka's algorithm)인데요. 사실은 이 알고리즘이 맨 처음으로 제시된 MST 알고리즘이라고 하더군요. 찾아보니 우리말로 된 자료도 곧잘 나올만큼 인지도가 꽤 있는 알고리즘이더군요. 명색이 알고리즘 공부한다는 사람이 이제야 이 알고리즘을 알게 되었다는 게 약간 부끄럽기도 합니다.
아무튼 보루프카 알고리즘과 관련하여 이번에 알게 된 사실들을 함께 공유하고자 이 글을 적습니다. 몇 개의 글을 더 적을 건데, 최종적으로는 평균적으로 \( O(|V| + |E|) \) 시간에 MST를 해결하는 랜덤 알고리즘을 소개할 예정입니다. 이 시간은 정렬과 서로소 집합 자료구조(disjoint-set data structure)를 필요로 하는 크루스칼 알고리즘이나 우선순위 큐(priority queue)가 필요한 프림 알고리즘으로는 쉽게 얻을 수 없는 수치죠. 확실하진 않지만, 아직까지 결정론적으로(deterministically) 선형 시간에 MST를 해결하는 방법은 없는 것으로 압니다. 그런데 보루프카 알고리즘을 활용하면 선형 시간을 기대할 수 있는 알고리즘을 만들 수 있다니 놀랍지 않나요?
문제 정의
너무도 유명한 문제인 만큼 어떤 문제인지는 간단히 정의만 하고 넘어가겠습니다. 입력으로는 방향이 없는 연결된(undirected connected) 그래프 \(G = (V, E)\)와 간선의 비용 \( c:E \to \mathbb{Q}\)가 주어집니다. 우리의 목표는 모든 정점을 연결하면서 순환(cycle)이 없는 신장 트리 \(T\) 중 비용 \(c(T)\)가 가장 저렴한 것을 찾는 것입니다.
이때 우리는 일반성을 잃지 않고 모든 간선의 비용이 서로 다르다고 가정할 수 있습니다. 다음의 작업을 거치면 되기 때문인데요. 먼저 모든 간선을 아무렇게나 일렬로 줄 지은 다음 앞에서부터 차례로 \(1, \cdots, |E|\)라고 번호를 붙여줍니다. 여기서 어떤 두 간선의 비용이 같다면 번호가 더 빠른 쪽의 간선이 더 작은 것으로 치는 겁니다. 여기서 얻은 MST가 원래 그래프에서도 여전히 MST가 되는 것은 쉽게 생각할 수 있습니다. 그럼 굳이 모든 간선의 비용이 다르다고 가정한 이유는 뭘까요? 간단합니다. 그러면 그래프에서 최소 신장 트리는 유일하기 때문이죠. 이는 아래 증명에서 빛을 발하게 됩니다.
그래프 축약(Contraction)
어떤 그래프 \(G = (V, E) \)에서 임의의 간선 \(e = (u, v)\)를 하나 갖고 오겠습니다. 여기서 \(e\)의 양 끝점 \(u\)와 \(v\)를 하나로 합친 그래프를 생각해 보겠습니다. 그러면 \( V \)에서는 \( u \)와 \(v\)가 빠지고, 대신 새로운 정점 \( \{ u, v \} \)가 들어오게 됩니다. \(E\)에서는 한쪽 끝이 \( u \)나 \(v\)인 간선은 모두 그 끝이 \( \{ u,v \} \)로 대체되겠죠. 중복된 간선은 그냥 그대로 두되, 만약 양 끝점이 둘다 \( \{u,v\} \)가 되는 루프의 경우에는 지워줍시다. 이 작업을 우리는 \(G\)를 \(e\)에 대해 축약(contract)한다고 하며, 그렇게 얻은 그래프를 \( G/e \)라고 부르겠습니다.
나아가 어떤 간선의 부분집합 \(F \subseteq E\)에 대해, \(F\)의 각 간선에 대해 축약한 그래프를 \(G/F\)라고 하겠습니다. 여기서 증명하지는 않겠지만, 간선을 어느 순서대로 축약해도 그 결과는 동일하며, 따라서 그 모두를 \(G/F\)라는 통일된 이름으로 불러도 괜찮습니다.
알고리즘
이제 알고리즘이 무엇인지 소개하겠습니다.
알고리즘 1. Borůvka's algorithm
입력: 방향이 없는 연결된 그래프 \(G = (V, E)\), 간선 비용 \(c : E \to \mathbb{Q}\)
출력: 신장 트리
- 만약 \(|V| = 1\)이면 해당 정점 하나를 반환한다.
- 각 정점 \(v \in V\)에 대해, \(v\)에 딸린(incident) 간선 중 가장 비용이 저렴한 간선 \(e_v\)를 찾는다.
- \(F \gets \{ e_v : v \in V \} \)
- 재귀적으로 \(G/F\)에서 MST \(T'\)을 찾는다.
- \( F \cup T' \)을 출력한다.
동작 예시
알고리즘의 동작을 다음 예시를 통해 찬찬히 설명드리죠. 다음 그림과 같은 그래프 \(G\)가 주어졌다고 하겠습니다.
단계 2에서는 각 정점마다 그에 딸린 간선 중 가장 비용이 저렴한 것을 찾습니다. 이를 모두 모아 놓은 것이 단계 2의 \(F\)입니다. 위 입력에서의 \(F\)는 다음과 같겠습니다.
어떤 간선은 두 개의 정점으로부터 선택을 받았을 수 있습니다. 예를 들어, 그림 4의 간선 \( (a, d) \)는 정점 \(a\)에 딸린 간선 중 가장 비용이 적을 뿐 아니라 \( d \)에 딸린 간선 중에서도 비용이 가장 저렴합니다. 그 후, 단계 4에서는 \(G/F\)를 구하고 재귀적으로 이 그래프에서 MST \(T'\)을 찾습니다.
최종적으로 단계 5에서는 앞에서 찾은 \(F\)와 \(T'\)을 합하고 이를 출력합니다.
분석 1. MST를 출력하는 이유
이제 알고리즘 1이 어째서 MST를 출력하는지를 증명하도록 하겠습니다. 앞에서 우리는 모든 간선의 비용이 서로 다르다고 가정하였기 때문에, 그래프에는 정확히 하나의 MST \(T^*\)가 존재하게 됩니다. 따라서 우리는 \(T^* = F \cup T'\)임을 보여야 합니다. 먼저 \(F\)가 잘 골라졌다는 것을 증명하도록 하죠.
정리 1. 최소 비용 간선과 MST의 성질
각 정점 \(v \in V\)에 대해, \(e_v \in T^* \)이다. 따라서 \( F \subseteq T^* \)이다.
[증명] 귀류법을 쓰기 위해, \(e_v \notin T^* \)라고 가정합시다. \(e_v\)에서 \(v\)가 아닌 다른 끝점을 \(u\)라고 하겠습니다. \(T^*\)는 신장 트리이므로 \(v\)에서 \(u\)로 가는 경로 \(P = \langle v, w, \cdots, u \rangle \)가 정확히 하나 존재합니다. 여기서 \(T^*\)에서 \( (v, w) \)를 제거하고 대신 \( e_v \)를 넣도록 합시다. 이렇게 얻은 \(T := T^* - (v, w) + e_v\)도 신장 트리가 됩니다.(직접 증명해 보시기 바랍니다.) 그런데 \( c(T) = c(T^*) - c(v,w) + c(e_v) \)이고, 정의에 의해 \( c(e_v) < c(v, w) \)이므로 \( T \)가 \(T^*\)보다 더 작은 비용을 갖습니다. 이는 \(T^*\)가 MST라는데 모순이 됩니다. ■
이 정리를 사용하여 \(F \cup T'\)이 실지로 MST가 된다는 것을 증명해 보도록 하죠.
정리 2. 알고리즘의 정확성
\( F \cup T' \)은 MST이다.
[증명] 먼저 알고리즘의 출력 \( F \cup T' \)이 실지로 신장 트리라는 것을 보여야 합니다. 이를 위해서는 임의의 두 정점이 그 위에서 서로 연결되어 있지만 순환은 존재하지 않음을 보이면 됩니다. 이 증명은 그리 어렵지 않으니 간략하게만 설명하고 자세한 내용은 생략하도록 하겠습니다. 첫 번째는 \(F\)를 통해 연결되지 않는 정점들은 \(T'\)의 간선을 타고 연결될 수 있다는 사실을 통해 보일 수 있습니다. 두 번째는 정리 1에서 \(F \subseteq T^*\)라서 \(F\)에 순환이 없다는 사실과 \(T'\)이 \(G/F\) 위의 신장 트리라는 사실을 통해 증명할 수 있습니다.
정리 1에서 이미 \( F \subseteq T^* \)임을 보였습니다. 따라서 남은 것은 \( T' \subseteq T^* \)임을 보이는 것인데, 이는 \( T^*/F \)가 \(G/F\) 위의 신장 트리가 된다는 것을 통해 대신 보일 수 있습니다. 이것이 충분한 이유는 \[ c(F \cup T') = c(F) + c(T') \leq c(F) + c(T^*/F) = c(T^*) \]가 되기 때문입니다. 자세한 내용은 생략하겠습니다만, 간단히 설명하자면 \(T^*/F\)가 만약 \(G/F\)에서 신장 트리가 아니라면 이는 \(T^*\)가 \(G\)에서부터 신장 트리가 아니라는 뜻이 되기에 모순을 일으키게 됩니다. ■
분석 2. 수행 시간
알고리즘 1의 수행 시간을 분석해 봅시다. 이 알고리즘은 내부에서 재귀적으로 \(G/F\)를 처리하므로 \(G/F\)의 크기가 원래 그래프에 비해 얼마큼 줄어드는지가 수행 시간 분석의 핵심입니다. 흥미롭게도 매번 정점의 개수가 절반 이하로 줄어들게 됩니다.
정리 3. 재귀 호출마다 줄어드는 입력
매번 \( V(G/F) \leq \frac{|V(G)|}{2} \)를 만족한다.
[증명] 먼저 \(|V(G/F)| = |V(G)| - |F|\)가 된다는 점을 확인하시기 바랍니다. \(F\)로 이루어지는 각 연결 성분(connected component)을 따져 봤을 때, 이들이 \(G/F\)에서는 정점 하나로 대체가 되므로 정확히 해당 연결 성분의 간선의 개수만큼 정점이 \(G\)에서 제거된다고 생각할 수 있기 때문입니다.
\(G\)의 모든 정점에서 정확히 하나의 간선을 골라 \(F\)에 넣고, 각 간선은 최대 두 개의 정점으로 부터 선택을 받을 수 있으므로 \( |F| \geq \frac{|V|}{2} \)를 보일 수 있습니다. 이 둘을 조합하면 정리의 부등식을 이끌어 낼 수 있습니다. ■
정리 3을 통해 우리는 알고리즘 1이 재귀적으로 호출되는 횟수가 \( O(\log |V|) \)가 된다는 것을 알 수 있습니다. 따라서, 나머지 단계의 수행 시간이 \( f(|V|, |E|) \)라고 했을 때, 알고리즘 1은 \( O( f(|V|, |E|) \cdot \log |V| ) \)에 동작한다는 것을 알 수 있습니다.
구현
남은 것은 \(f(|V|, |E|)\)를 구하는 것이죠. 이를 위해서 보루프카 알고리즘의 한 가지 구현을 제시하고자 합니다. 이 구현은 심지어 알고리즘 1에서 사용했던 재귀 호출을 사용하지도 않으므로 원래보다 효율적인 구현이라고 할 수 있겠습니다.
알고리즘 2. An implementation of Borůvka's algorithm
입력: 방향이 없는 연결된 그래프 \(G = (V, E)\), 간선 비용 \(c : E \to \mathbb{Q}\)
출력: 신장 트리
- \(F \gets \emptyset \)
- \( |F| = |V| - 1 \)이 될 때까지 아래를 반복한다.
- DFS/BFS를 수행하여 \( (V,F) \)의 연결 성분을 구한다.
- 각 연결 성분 \(C\)에 대해 \( e_C \gets \mathsf{nil} \)
- 각 간선 \( e=(u,v) \)에 대해, \(u\)와 \(v\)가 각각 서로 다른 연결 성분 \(C_1\), \(C_2\)에 속했다면, 아래를 수행한다.
- \(e_{C_1} = \mathsf{nil}\)이거나, \( c(e) < c(e_{C_1}) \)이면, \( e_{C_1} \gets e \).
- \(e_{C_2} = \mathsf{nil}\)이거나, \( c(e) < c(e_{C_2}) \)이면, \( e_{C_2} \gets e \).
- 각 연결 성분 \(C\)에 대해, \( e_C \)를 \(F\)에 넣는다.
- \(F\)를 반환한다.
알고리즘 2의 단계 2-a에서 \( (V,F) \)의 연결 성분을 모두 구한 후, 서로 다른 연결 성분의 간선인 경우에만 단계 2-c에서 고려하는 것은 곧 알고리즘 1에서 \(G/F\)의 간선들만 고려하는 것과 동일합니다. 따라서 알고리즘 2가 알고리즘 1의 한 가지 구현 방법이 되는 것이죠.
단계 2가 한 번 동작할 때 걸리는 시간은 \( O(|E|) \)입니다.(\(G\)는 연결된 그래프이므로 \( |E| \geq |V| - 1 \)입니다.) 앞에서 단계 2를 총 \( O(\log |V|) \) 수행한다고 하였으므로 이 알고리즘의 수행 시간은 \( O(|E| \log |V|) \)가 됩니다.
마치며
이것으로 보루프카 알고리즘에 대한 설명을 모두 마치겠습니다. 서론에서도 설명을 드렸다시피, 이 알고리즘은 최소 신장 트리 문제를 해결하는 방법 중 가장 먼저 제시된 알고리즘입니다. 다른 유명한 방법인 크루스칼 알고리즘이나 프림 알고리즘과 달리, 이 알고리즘은 여러 흥미로운 특징들을 갖고 있습니다. 하나는 알고리즘 자체의 특징 덕분에 병렬 컴퓨팅(parallel computing)이나 분산 컴퓨팅(distributed computing)에 적합하다는 것입니다. 참고로 병렬 컴퓨팅 분야에서는 특히 이 알고리즘을 솔린 알고리즘(Sollin's algorithm)이라고도 부른다고도 하네요.
다른 하나는 이 알고리즘을 기초로 다양한 문제를 해결할 수 있다는 점입니다. 실례로 어떤 그래프와 그 위의 신장 트리 하나가 입력됐을 때, 주어진 신장 트리가 최소 신장 트리인지를 판단하는 문제도 여기서 배운 아이디어를 활용하면 선형 시간에 해결할 수 있습니다. 또한, 선형 기대 시간에 MST를 찾는 랜덤 알고리즘도 보루프카 알고리즘에 기반을 두고 있습니다. 이와 관련된 내용은 나중에 다루어 보도록 하겠습니다.
본문에서 \(G\)를 연결된 그래프라고 가정하였습니다. 그럼 연결되지 않은 그래프에서 이 알고리즘을 돌리면 어떻게 될까요? 이때는 최소 신장 포레스트(minimum spanning forest)를 출력하게 됩니다. 다만 최소 신장 포레스트는 결국 각 연결 성분에서 MST를 찾는 것과 동일하기 때문에 본문에서는 그냥 연결된 그래프에서만 고려하였습니다.
궁금하신 점이 있으시거나, 글에 오류가 있는 경우에는 알려주세요. 고맙습니다. :)
참조
[1] Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge university press, 1995.
'조합론적 최적화 > Minimum spanning tree' 카테고리의 다른 글
| 절단 성질을 이용한 MST 알고리즘 증명 (Proving MST Algorithms by Cut Property) (4) | 2022.06.21 |
|---|
