Minimum Spanning Trees

주어진 마을에 여러 집과 이를 연결하는 도로가 있다. 각 도로는 두 개의 집을 연결하며, 도로를 수리하는데 비용 w(u, v)이 소요된다. 목표는 최소 비용으로 필요한 도로만 수리하여 모든 집이 서로 연결되도록 하는 것이다. 이 문제는 MST를 구하는 알고리즘으로 해결할 수 있다.

수리할 도로 집합 T⊆E를 찾으며, 이때 T는 모든 정점을 연결하면서 최소 비용을 만족하는 스패닝 트리가 되어야한다.

 

최소 비용 스패닝 트리(Minimum Spainning Tree)란, 주어진 그래프의 모든 정점을 연결하는 모든 스패닝 트리 중에서 가중치의 합이 최소가 되는 트리를 의미한다.

MST

 

위 그림에서 두껍게 칠해진 선들의 집합을 MST라고 한다. 모든 노드들을 연결하고 있으며, 도합 37이라는 최소 비용을 가지고 있다.

간선 (b, c)의 가중치가 8인데, 간선 (a, h)의 가중치도 8인걸 볼 수 있다. 이때, 간선 (a, h)를 선택하더라도 모든 노드들을 연결하며 비용도 달라지지 않기에 간선 (b, c) 대신 사용해도 괜찮다.

따라서, 한 그래프에 여러 개의 MST가 존재할 수도 있다.

---

MST를 구성하는 방법

다음은 MST의 속성이다.

• |V| -1 개의 간선을 가진다. 여기서 |V|는 정점의 수를 뜻한다.
• 사이클을 포함하지 않는 트리다.
• MST는 반드시 하나로 결정되는 것이 아니라, 경우에 따라 여러 개의 MST가 존재할 수 있다.

MST를 구성하기 위해, 초기에는 집합 A를 구성할 간선 집합으로 정의하고, 간선이 하나도 없는 상태로 시작한다.

이제 A에 간선을 하나씩 추가하는데, MST의 속성을 만족하도록 유지해야하며, A에 포함된 간선들이 여전히 MST의 부분집합이 되도록 유지한다. A에 추가되어도 MST의 부분집합을 유지할 수 있는 간선을 Safe edge(안전한 간선)이라고 하며, 이 안전한 간선들만이 A에 추가될 수 있다.

A에 safe edge를 추가하는 알고리즘

 

루프 불변성을 사용하여 이 일반적인 알고리즘이 작동함을 보이겠다.

• 초기화: 공집합은 자명하게 루프 불변성을 만족한다.
• 유지: 우리는 안전한 간선만을 추가하므로, A는 항상 어떤 MST의 부분집합으로 남는다.
• 종료: A에 추가된 모든 간선은 MST에 속하므로, 알고리즘이 종료되었을 때 A는 spanning tree이며 MST이다.

그럼 안전한 간선은 어떻게 찾는걸까?

 

그래프에 가장 낮은 가중치를 갖는 간선 (h, g)가 있다고 가정해보자. A = 0일 때, 이 간선은 안전할까?

$S \subset V$는 h를 포함하지만 g는 포함하지 않는 노드 집합으로 설정해보자. 즉, g는 (V - S)에 있는 것이다. 여기서 모든 MST에는 S와 V-S를 연결하는 간선이 최소 한개는 있어야한다. MST에서는 모든 노드를 연결해야하기 때문이다. 이때, (h, g)가 이 간선에 해당된다면, 최소 가중치의 간선을 선택하지 않을 이유가 없다.

 

다른 정의를 살펴보자. $S \subset V$이고 $A \subseteq E$이다.

Cut (S, V-S)는 노드를 서로소 집합 S와 V-S로 나누는 분할이다. 간선 $(u, v) \in E$는 cut(S, V-S)를 가로지른다고 가정해보자. 이는 한 끝점이 S에 있고 다른 끝점이 V-S에 있을 때 성립한다.

Cut은 A를 respect한다고 할 때, 이는 A에 있는 어떤 간선도 그 cut을 가로지르지 않을 때 성립한다. light edge란 해당 cut을 가로지르는 모든 간선 중에서 가중치가 최소인 간선을 의미한다. 주어진 cut에 대해 하나 이상의 라이트 엣지가 존재할 수 있다.

 

Theorem. A가 MST의 부분 집합이고, (S, V-S)가 A를 존중하는 cut이며, (u, v)가 (S, V-S)를 가로지르는 라이트 엣지라고 가정한다. 이 경우 (u, v)는 A에 대해 안전할 것이다. 

Proof. T는 A를 포함하는 MST라고 하자. 즉, $A \subseteq T$ 이다.

만약 $(u, v) \in T$라면 증명이 완료된다. 즉, $A \cup (u, v) \subseteq T$이다.

 

만약 $(u, v) \in T$가 아니라고 가정해보자. 우리는 $A\cup(u, v)$를 포함하는 새로운 MST T'을 구성한다. 여기서 T는 MST이므로 u와 v 사이에서는 고유 경로 p가 포함되어 있다. 경로 p는 (S, V-S)를 적어도 한 번은 가로질러야한다. p가 cut을 가로지르는 간선을 (x, y)라고 한다면, $w(u, v) \leq w(x, y)$라는 모순이 발생한다.

모순이 발생하면, 기존의 MST T에서 (x, y)를 제거하고 (u, v)를 추가함으로써 T'를 구성할 수 있다(T′=T−{(x,y)}∪{(u,v)}). T'은 T와 같은 가중치를 가지므로 T'또한 MST가 되고, 따라서 (u, v)는 A에 대한 안전한 간선인 것이 증명된다.

 

Generic-MST에서 A는 연결된 컴포넌트들로 구성된 forest다. 초기에는 각 단일 컴포넌트가 단일 정점으로 구성된다. 안전한 간선을 추가할 때마다 두 컴포넌트가 하나로 합쳐지며, 각 컴포넌트는 tree이다. MST는 정확히 |V| -1개의 간선을 가지므로, while 루프는 |V| -1번 반복된다. 이는 |V|-1개의 안전한 간선을 추가한 후에는 하나의 컴포넌트로 축소된다는 것을 의미한다.

 

 

Corollary. 만약 $C = (V_C, E_C)$가 $G_A = (V, A)$에서 forest에 연결된 컴포넌트이고, (u, v)가 C와 다른 컴포넌트를 연결하는 라이트 엣지라면, (u, v)는 A에 대해 안전하다.

Proof. 정리에서 $S = V_C$로 설정한다. 이와 같은 과정은 MST 문제를 해결하기 위한 Kruskal 알고리즘으로 이어진다.

---

Kruskal's Algorithm

 

크루스칼 알고리즘에서 G = (V, E)는 연결된 무방향 가중치 그래프이다. 가중치 함수 w: E > R는 간선의 가중치를 나타낸다.

크루스칼 알고리즘 수도 코드

 

알고리즘이 어떻게 동작하는지 알아보자.

각 노드가 처음에는 자기 자신의 컴포넌트로 시작한다. 두 컴포넌트를 하나로 병합하기 위해, 해당 컴포넌트를 연결하는 가장 가벼운 간선을 선택한다. 즉, 이 간선은 두 컴포넌트를 나누는 cut을 가로지르는 라이트 엣지이다.

• Make set 연산: 주어진 요소를 포함하는 집합을 생성한다. 이 알고리즘에서는 부모 노드가 없기 때문에 자기 자신을 가리킨다.
• Find set 연산: 어떤 원소가 주어졌을 때 이 원소가 속한 집합의 대표 원소를 반환하는 연산이다.
• Union 연산: 두 개의 집합을 하나로 합치는 연산이다.

간선 집합을 가중치에 따라 오름차순으로 정렬하고, 서로 다른 컴포넌트에 속하는 노드를 연결하는 간선을 찾기 위해 disjoint-set data structure(분리 집합 자료 구조)를 사용한다.

 

크루스칼 알고리즘에서 사용하는 자료구조를 보면, 위와 같다.

Union이란 두 노드가 주어졌을 때, 이 노드들을 한 그래프로 합치는 알고리즘이다.

h노드와 g노드를 Union할 때,  g의 포인터가 h를 가리키게된다. 포인팅 당하는 h 노드는 대표자라고 한다.

여기서 i노드를 추가하려고 할때, i의 포인터는 g의 포인터를 가리키는 것이 아닌 대표자 h노드를 가리키게 된다.

동일한 대표자를 가지는 노드들은 동일한 그룹으로 묶인다.

 

따라서 수도코드의 6번줄을 보면, u 노드와 v 노드의 대표자가 같은지 보고, 같지 않으면 간선을 추가하게 되는 것이다.

대표자가 같으면 이미 동일한 그룹으로 묶여있는, 간선으로 이미 연결되어 있는 상태이기 때문이다.

 

크루스칼 알고리즘의 시간 복잡도를 분석하자.

• A를 빈 집합으로 초기화 하는 시간 $O(1)$이 걸린다.
• 첫번째 for 루프의 |V|개의 노드에 대해 MAKE-SET을 호출하는 시간 $O(|V|)$이 걸린다.
• 모든 간선 E를 정렬하는 시간 $O(|E|log |E|)$이 걸린다.
• 두번째 for루프의 |E|개의 간선에 대해 FIND-SET 및 UNION을 호출하는 시간 $O(|E|\alpha(|V|))$이 걸린다.
• 총 시간 복잡도는 $O((V+E)\alpha(|V|))+O(|E|log |E|)$이다.

G가 연결되어 있는 경우, 간선의 수는 노드의 수와 관계를 가지게 된다. $|E| \geq |V| -1$

간선의 수가 노드의 수보다 크거나 같기 때문에, O(|V|)가 생략되어 $O(E\alpha(V))+O(ElgE)$가 된다.

$\alpha(V)$는 매우 느리게 증가하는 함수로, 거의 상수에 가깝기 때문에 간선의 정렬 시간이 지배적이게된다.

따라서 총 시간 복잡도는 $O(E\log E)$가 된다.

 

그래프가 밀집되어 있는 경우, $|E| \leq|V|^2$가 된다.

이 경우 lg |E|가 O(2lg V)= O(lg V)로 표현될 수 있으므로, $O(E\log V)$가 된다.

 

만약 간선들이 이미 정렬된 상태라면, $O(E\alpha(V))$가 될 수도 있다.

---

Prim's algorithm

프림 알고리즘은 한 번에 한 개의 트리를 구축하며, 집합 A의 간선들은 항상 하나의 단일 트리를 형성한다.

임의의 루트 r에서 시작하여 트리가 모든 노드 V를 포함할 때까지 확장된다. 

각 단계에서, $(V_A, V-V_A)$라는 cut을 가로지르는 light edge를 찾는다. 여기서 $V_A$는 현재 A에 포함된 간선들이 연결된 정점들을 의미한다. 찾은 light edge를 A에 추가하며, 이는 A에 대해 안전한 간선이 된다.

알고리즘이 종료되면 A의 간선들은 MST를 형성한다.

 

light edge는 어떻게 찾을까?

프림 알고리즘에서는 우선순위 큐를 사용한다.

각 객체는 $V-V_A$에 속하는 노드이고, 노드 v의 key는 $u \in V_A$인 노드와 연결된 모든 간선 (u, v)중 가장 작은 가중치를 나타낸다.

EXTRACT-MIN 연산은 가장 작은 키를 가진 v를 반환하며, 가장 가벼운 간선 (u, v)를 찾는데 사용된다.

만약 key 값이 무한대인 경우, 해당 v는 $V_A$에 있는 어떤 노드와도 인접하지 않ㄴ다.

 

결과적으로 A의 간선들은 루트 r을 가진 트리를 형성하게 된다.

r은 알고리즘의 입력으로 주어지며, 임의의 노드가 될 수 있다.

각 노드는 트리에서 자신의 부모를 $\pi[v]$ 속성으로 저장한다. $\pi[v] = NIL$인 경우는 v=r 이거나, v가 아직 부모를 가지지 않은 상태이다.

 

알고리즘이 진행됨에 따라 $A = (v, \pi[v]): v \in V -r -Q$이 되고, 알고리즘 종료 시 $V_A = V$가 된다. 우선 순위 Q는 비어있는 상태가 되고, MST는 다음과 같이 정의된다: $A = (v, \pi[v]): v \in V -r$

프림 알고리즘 수도코드

 

각 노드에 대해 무한대 값으로 초기화 시켜주고, 부모 노드가 없는 상태로 만든다.

임의의 루트 노드 r의 값을 0으로 설정시켜주고, 그래프를 Q에 넣는다.

Q가 0이 아닐 동안, 노드 u에 가장 작은 가중치를 가진 노드를 주고, 인접한 노드 v들의 간선 가중치 값을 업데이트 한다.

처음에는 인접한 노드들의 key값이 모두 무한대일 것이고, 당연히 가중치의 값이 더 작을 테니 인접한 노드들에 대한 가중치 값이 업데이트 된다. 이는 11번째 줄에서 시행되며, DECREASE-KEY연산을 수행하게 된다.

 

예시를 들어 설명해보자.

(a)에서 루트 노드로 a를 설정했다. 루트 노드의 값은 0으로 설정해주니까 Q에는 노드의 값들이 오른쪽 그림 a)처럼 들어가 있고, u에는 a노드가 들어가게 된다. 

(b) u였던 a노드의 가중치(루트니까 0)을 $V_A$에 넣어주고, a와 인접한 노드들의 가중치 값을 업데이트 한다. b노드와 연결된 간선의 가중치가 제일 작기 때문에 u에는 b노드가 들어가게된다.

(c) u였던 b노드와 부모 a노드를 연결하는 간선이 light edge가 되니 $V_A$에 넣어주고, b와 인접한 노드들의 가중치 값을 업데이트한다. c와의 연결과 h와의 연결 가중치 값은 동일하지만, 이 예시에서는 c를 택했다. 따라서 u에는 c노드가 들어가게 된다.

 

위 내용을 반복하면 Q에는 아무것도 남지 않게되고, 알고리즘이 종료된다.

 

프림 알고리즘의 시간 복잡도는 우선순위 큐의 구현 방식에 따라 달라진다. 여기서는 binary heap을 사용한 경우를 분석한다.

• 초기화 및 첫번째 for 루프: 우선순위 큐를 초기화하고 각 노드에 대해 초기 key 값을 설정하는 시간은 $O(V\lg V)$가 걸린다. 루트 노드의 key 값을 설정하는 DECREASE-KEY연산은 $O(\lg V)$가 걸린다.
• while 루프: 각 정점 v에 대해 두가지 연산을 수행한다. |V| EXTRACT-MIN 연산은 V번 호출하므로 $O(V\lg V)$가 걸린다. |E| DECREASE-KEY 연산은 E번 호출하므로 $O(E\lg V)$가 걸린다.
• 총 시간 복잡도는 $O(V\lg V)+O(E\lg V)$이므로, $O((V+E)\lg V)$가 된다.

---

** 대학교 수업을 듣고 이해한 부분을 최대한 풀어서 작성한 글입니다.

틀린 정보가 존재할 수 있으며, 언제나 피드백은 환영입니다. **