Minimum Spanning Tree (MST)

안녕하세요!

오늘은 Minimum spanning tree 에 대해서 정리해보려고 합니다.

 

저는 ... 아는게 없는 감자이기 때문에 ..

 

https://victorydntmd.tistory.com/98

[알고리즘] MST(1) - 최소 신장 트리(Minimum Spanning Tree)

해당 블로그를 참고하여 작성했습니다 !!

늘 모든 블로거분들에게 감사합니다 !!!

 

1.  최소 신장 트리란

 

최소 신장 트리 (Minimum Spanning Tree)

 

최소 신장 트리(MST)란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다.

이전 글에서 살펴봤던 BFS,DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했습니다.

MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다.

 

아래의 예제를 살펴봅시다.

 

MST는 이와 같이 연결된(connect) 무방향(undirected)의 가중치(weight) 그래프를 가정합니다.

각 간선의 가중치들은 방금 전에 언급한 비용(cost)을 의미합니다.

 

다시 말하면 MST는 모든 정점을 연결하는 트리를 생성하는데,

그 규칙으로써 가중치(비용)의 합을 최소화하는 트리를 찾는 것이 목적입니다.

 

우선 우리는 각 간선들의 비용을 정렬해야합니다. 왜냐하면 MST의 정의대로 비용이 가장 적은 간선들이 연결되어 트리를 생성해야하기 때문입니다.

MST의 결과는 다음과 같습니다.

 

MST의 핵심은 cycle을 형성되지 않도록 하는 것입니다.

 

또한 현재 예제에서는 MST가 오직 한 개의 트리 밖에 생성할 수 없습니다.

그러나 만약, (v1, v4) 간선이 없다고 가정한다면,

(v1, v3) 간선 또는 (v4, v5) 간선이 선택될 수 있습니다.

 

즉 이 경우에는 두개의 트리를 생성할 수 있습니다.

 이 처럼 MST는 여러개의 트리를 생성할 수 있습니다.

즉 그래프에서 신장 트리는 여러 형태로 존재할 수 있으며, 신장 트리의 특징은 n개의 정점을 갖는 그래프에서 신장 트리에 속하는 간선의 수는 n-1개이며 사이클을 이루지 않는다는 특징이 있습니다.

 

MST를 이용하는 대표적인 알고리즘은 Kruskal, Prim 이 있습니다.

 

이에 대해 알아보기 앞서 MST의 주요 용어에 대해 알아보겠습니다.

 

2. 주요 용어

MST에서 핵심이 되는 용어는 안전간선(safe edge)입니다.

안전간선을 정의하기 위해서는 4가지의 용어가 필요하므로, 이 용어들을 살펴보고 안전 간선을 정의하도록 하겠습니다.

 

1) 단절

단절은 트리의 모든 정점들의 집합을 V라고 할 때, 어떤 정점들의 집한 S가 있어서 두개의 단순 집합 (S, V-S) 로 나누는 것을 의미합니다.

단순히 모든 정점들을 두 집합으로 분리했다고 생각하면 됩니다.

 

2) 교차한다

단절된 두 집합 (S, V-S)에 대해, 간선 (u,v) 의 한 종점이 S, 다른 종점이 V-S에 속한다면 간선(u,v)는 단절(S, V-S)와 교차한다고 합니다.

3)따른다

MST의 부분집합 A에 대해 단절을 건너는 간선이 없다면 단절이 집합 A를 따른다고 합니다.

여기서 파란색 간선들을 MST의 결과가 될 트리의 부분집합입니다.

즉 A는 파란색 간선들을 모두 갖는 집합이라고 할 수 있습니다.

 

단절이 A를 따른다는 것은 A의 간선 중 단절과 교차하는 것이 없다는 것을 의미합니다.

따라서 1번 그림은 단절이 A를 따르지만, 2번 그림은 단절이 A를 따르지 않습니다.

 

4) 경량간선

단절과 교차하는 간선 중 가중치가 최소인 간선을 경량간선이라고 합니다.

 

5) 안전간선

연결된 무방향 그래프 G=(V,E)에 대해서 A를 MST의 부분집합이라고 하고,

(S, V-S)가 A를 따르는 어떤 단절이라 하며,

(u, v)를 단절과 교차하는 경량간선이라고 할 때,

(u,v)는 A의 안전간선이라고 합니다.

 

MST의 대표적인 알고리즘으로는 Kruskal's 알고리즘과 Prim's 알고리즘이 있습니다.

 

이 둘은 모두 MST를 구하는 방법 중 하나입니다. 또한 둘다 Greedy Method를 기초로 합니다. 이는 당장 눈 앞의 최소 비용을 선택해서 결과적으로 최적의 Solution을 찾기 때문입니다.

 

다만 차이점이 있다면,

Kruskal's 알고리즘은 간선 위주의 알고리즘,

Prim's 알고리즘은 정점 위주의 알고리즘이라는 것입니다.

 

Kruskal's 알고리즘은 시작점을 정하지 않고, 최소 비용의 간선을 차례대로 대입하면서 MST를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야합니다. 사이클을 확인하는 방법으로는 Union - Find (Disjoint-Set) 방법이 있습니다.

 

Prim's 알고리즘은 시작점을 정하고, 시작점에서 가까운 정점을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않습니다.

 

시간 복잡도는 비슷하지만, 일반적으로 Dense한 그래프릐 경우 프림이, 그렇지 않은 경우에는 크루스칼이 유리합니다.

크루스칼은 간선을 weight 기준으로 정렬하는 과정이 오래 걸리며, 프림의 경우 최소 거리의 정점을 찾는 부분에서 자료구조의 성능에 영향을 받습니다. 

 

- 프림 : O(V^2+E) → O(E logV)

- 크루스칼 : O(E logE)

 

 

 

3. Kruskal's Algorithm

 

MST의 첫번째 알고리즘으로 Kruskal's 알고리즘을 살펴보겠습니다.

MST는 주어진 그래프에서 안전 간선을 연결하여 최소한의 비용으로 이루어진 트리를 만드는 것이 목적입니다.

Kruskal's 알고리즘은 안전 간선을 연결할 때 Union - Find 자료구조를 이용합니다.

위의 자료구조를 이해하는 것이 Kruskal's 알고리즘의 핵심이므로 이 내용을 먼저 살펴보겠습니다.

 

(1). Union - Find

Union - Find 자료구조는 이름 그대로 "찾고 합치는 과정"입니다.

 

예를 들어, 3개의 트리가 있다고 하겠습니다.

 

 

이 트리들은 정점 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8이 각각 집합을 이루고 있다가 Union이 진행된 중간 단계입니다.

즉 {1, 2} | {3, 4, 5} | {6, 7, 8} 이렇게 3개의 집합으로 나뉜 것을 표현했습니다.

 

각 트리를 집합이라고 표현할 때 대표 값은 그 집합을 대표하는 값입니다.

트리 A의 모든 노드들을 대표 값으로 1을 갖고 있으며, 트리 B의 모든 노드들을 3, 트리 C는 6을 대표 값으로 갖습니다.

대표 값이 필요한 이유는 두 정점을 합칠(Union) 때 서류 같은 집합인지 아닌지 확인(Find) 하기 위함입니다.

 

예를 들어, 위의 그림에서 1과 2를 합친다고 할 때 두 정점은 대표 값이 1이기 때문에 서로 같은 집합입니다.

그래서 1과 2는 합치는 작업을 하지 않습니다.

사실 1과 2는 이미 Union이 진행된 상태였기 때문에 같은 부모를 갖게 되죠.

바로 뒤에서 갈펴보겠지만 서로 다른 대표 값을 갖는 두 집합을 Union 하면 대표값을 통일함으로써 Union을 수행합니다.

잉 때 두 정점의 대표 값을 확인한 작업이 Find 연산입니다.

 

다른 예로, 2가 속한 트리 A와 5가 속한 트리 B는 합칠 수 있을까요?

두 집합의 대표 값은 1과 3으로 다르기 때문에(Find) Union이 가능합니다.

그 결과는 아래 그림과 같습니다.

 

코드를 구현하는 방식에 따라 두 가지 경우가 됩니다.

트리 B가 A에 흡수 되면 1, 2, 3, 4, 5 모든 정점의 대표 값은 1이 되고, 트리 A가 B에 흡수되면 대표 값은 3이 됩니다.

 

 

이런 식으로 두 정점(집합)을 합칠 때 대표 값을 확인하는 작업이 Find 연산이고,

만약 두 집합의 대표 값이 다르면 두 집합을 합치는 작업이 Union 연산입니다.

 

Union - Find 자료 구조를 이해하셨다면 Kruskal's 알고리즘은 매우 쉽습니다.

 

 

(2). Kruskal's 알고리즘

 

Kruskal's 알고리즘은 트리를 연결하는 모든 간선 중 가장 작은 간선(u, v)를 찾아 MST의 부분 집합에 추가합니다.

 

그래프의 초기 모습이 아래와 같을 때, kruskal's 알고리즘의 진행 방식을 살펴보겠습니다.

각 정점안에 있는 숫자는 정점의 이름이고, 색깔은 집합(대표 값)을 의미합니다.

즉 초기 값으로 모든 정점에 대해 각 정점이 하나의 집합을 이루도록 합니다.

편의상 색깔을 대표하는 값으로 표현하겠습니다.

 

 

가중치가 가장 작은 간선(3, 6)을 선택합니다.

Step 1에서 정점 3은 밝은 회색이고, 정점 6은 진한 파란색이므로 두 정점은 다른 집합입니다.

이처럼 Find 연산을 통해 대표 값을 확인하였고, 두 집합이 다른 것이 확인되었으므로 Union을 수행합니다.

두 정점의 색깔을 밝은 회색으로 표현해도 좋고, 진한 파란색으로 표현해도 좋습니다. 

 

가중치가 2인 간선 다음으로 가중치가 작은 간선 (5,7)을 선택합니다.

Step 2에서 두 정점 5와 7의 색깔은 다르므로 다른 집합입니다.

따라서 union을 수행합니다.

 

이 후의 과정은 step 2와 stap3 와 같습니다.

가장 작은 간선을 차례대로 선택하여 양 끝의 정점의 집합이 같은지 다른지 Find를 수행하고, Union을 할지 말지 결정합니다.

 

kruskal's 알고리즘은 가장 작은 간선을 차례대로 뽑아 간선을 잇는 두 정점의 집합을 비교하여 Union - Find 연산을 수행합니다.

MST는 최소합의 비용으로 이루어진 트리를 만드는 것이 목적이므로 Kruskal's 알고리즘은 이를 만족합니다.

 

(3). 수도 코드

1) line 1

A는 Kruskal's 알고리즘의 결과가 되는 트리의 집합입니다.

어떤 간선이 선택되서 간선을 잇는 두 정점이 다른 집합이면 이 간선을 A에 추가함으로써 Kruskal's 알고리즘의 결과를 생성합니다.

 

2) line 2 - 3

그래프의 모든 정점을 집합으로 만듭니다.

Step1에서 모든 정점들의 색깔이 다른 색이었죠?

그렇게 표현한 이유는 모든 각 정점이 하나의 집합을 이루고 있다고 했기 때문입니다.

 

3) line 4

각 Step을 진행할 때 마다 최소의 가중치를 갖는 간선을 선택했습니다.

MST는 최소의 비용을 갖는 트리여야 하므로 최소의 가중치를 갖는 간선이 먼저 선택되어야합니다.

따라서 간선들의 가중치를 오름차순으로 정렬시킵니다.

 

4) line 5 -8

모든 간선에 대해서 Find 연산을 수행합니다.

이 때 간선은 line 4에서 정렬을 시켰으므로 뽑기만 하면 됩니다.

그리고 Find 연산의 결과 두 집합이 다르면 현재의 간선을 집합 A에 추가시키고 간선을 잇는 두 정점을 Union 합니다.

실제로 Find 를 한다는 것은 두 정점의 대표 값을 확인하는 것이며, Union한다는 것은 두 정점의 대표값을 합치는 것입니다.

 

다시한번 정리하면 Kruskal's 알고리즘은 간선들의 가중치를 오름차순으로 정렬하고, 간선들을 차례로 선택해서 간선을 잇는 두 정점의 Find 연산을 수행한 뒤, 두 집합이 다르면 Union 연산을 수행하는 알고리즘입니다.

 

크루스칼의 핵심은 모든 간선을 가중치 기준으로 오름차순으로 정렬하고,

이 간선들을 순서대로 모든 정점이 연결될 때까지 연결하는 것입니다.

Union-Find 알고리즘을 이용해서 구현할 수 있고, 이를 통해 사이클이 형성되지 않으면서 모든 정점을 연결할 수 있습니다.

4. Prim's Algorithm

 

Prim's 알고리즘은 BFS와 같이 시작점을 기준으로 간선이 확장해나가는 방식입니다.

대신 Prim's 알고리즘은 간선에 가중치가 있으며, 최소한의 비용을 갖는 트리를 만들어야한다는 점에서 차이가 있습니다.

 

Prim's 알고리즘에서는 특별히 사전에 알아둬야할 내용이 없으므로 바로 어떻게 동작하는지 알아보도록 하겠습니다.

 

(1). Prim's 알고리즘

 

Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후, 

그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다.

 

초기 그래프입니다.

모든 정점들의 key 값은 inf가 할당되어 있습니다.

그 이유는 Prim's 알고리즘이 최소 우선 순위 큐에서 각 정점의 key 값들 중 최소 값을 뽑아 그 정점을 이용하여 다음 단계를 진행하기 때문입니다. 그래서 어떠한 가중치보다 큰 값으로 설정하기 위해 inf를 할당합니다.

 

start vertex를 설정합니다.

Prim's 알고리즘은 어떤 vertex를 start로 하든 항상 같은 트리가 형성됩니다.

 

start vertex는 초기 값으로 key 값을 0으로 할당합니다.

 

Step2 에서 큐에는 {0, inf, inf, inf, inf, inf, inf} 원소들이 있고, 그 중에서 0이 가장 작으므로 start vertex가 선택됩니다.

 

선택된 vertex에 대해서 인접 간선의 가중치와 정점의 key 값을 확인합니다.

즉 Step  4 ~ Step 7 은 하나의 큰 단계라고 보시면 됩니다.

수도 코드에서 이를 반복문으로 표현하고 있습니다.

 

첫번째로 가중치가 9인 간선을 확인합니다.

Step 3 에서 start vertex와 가중치가 9인 간선으로 연결된 정점의 key 값은 inf 였습니다.

즉 가중치 = 9, key 값 = inf

9 < inf 이므로 key 값을 가중치의 값으로 바꿔줍니다.

 

이것이 Prim's 알고리즘이 MST를 만드는 규칙입니다.

그리고 key 값이 변경된 정점의 부모는 start vertex 라는 것을 표현하기 위해 화살표로 표시하겠습니다.

 

 

 

 

이제 start vertex 에 대해서 모든 간선들을 확인해보았습니다.

그러면 이제 다음 정점을 선택하기 위해 최소 우선순위 큐에서 key 값이 가장 작은 정점을 고릅니다.

지금 우선 순위 큐에는 {5, 7, inf, 6, inf, 9} 가 있으므로 가장 작은 값은 5입니다.

Step 9 부터는 key 값이 5인 정점에 대해 Step 4 ~ Step 7의 과정을 수행할 것입니다.

 

key의 값이 5인 정점과 연결된 간선을 보니 가중치가 10인 간선이 있고, 이 간선과 연결된 정점의 key 값은 7입니다.

가중치 = 10 > 7 = key 값 이므로 key 값을 변경하지 않습니다.

 

key 값을 변경하는 것은 가중치보다 key 값이 더 클 경우에만 해당됩니다.

연결된 간선이 1개 밖에 없으므로 다시 최소 우선순위 큐에서 또 정점을 골라야합니다.

 

다음에 선택된 정점은 key 값이 6인 정점입니다.

인접한 간선들의 가중치는 12, 11, 15 이네요.

 

step 10 에서 가중치가 15인 간선에 대해, 이 간선과 연결된 정점의 key 값은 inf 이므로 가중치 = 15 < inf = key 값, 따라서 key 값을 변경합니다.

 

이 전 단계와 같습니다.

 

가중치 = 12 < 7 = key 값이므로 key 값을 변경하지 않습니다.

 

우선 순위 큐 중에서 가장 작은 정점이 선택됩니다.

 

연결된 간선 중 가중치가 2인 간선에 대해, 연결된 정점의 key 값은 11입니다.

가중치 = 2 < 11 = key 값이므로 key 값을 변경합니다.

 

이 때 key 값이 변경되는 정점은 이미 가중치가 11인 간선을 갖고 있었습니다.

그런데 key 값이 새로 변경되었으므로 부모를 갱신해야합니다.

 

 

 

Prim's 알고리즘은 최소 우선순위 큐에서 key 값이 작은 정점을 고른 후 그 정점의 인접한 간선의 가중치와 연결된 정점의 key 값을 비교해서 연결된 정점의 key 값을 갱신할지 말지 결정하는 것을 통해 MST를 구현합니다.

 

(2). 수도 코드

 

 

1) line 1 ~ 3

그래프의 모든 정점에 대해 key 값을 inf 로 할당하고, 부모를  NULL로 할당합니다.

 

2) line 4 ~ 5

시작 정점의 key 값을 0으로 하고, 그래프의 모든 점을 최소 우선 순위 큐에 삽입합니다.

 

3) line 6 ~ 7

최소 우선순위 큐가 비어있을 때까지 반복문을 수행하며, 매 반복마다 key 값이 최소인 정점을 추출합니다.

 

4) line  8 ~ 11

추출한 정점의 모든 인접한 정점에 대해 ,

가중치와 정점의 key 값을 비교해서 key 값이 더 크면 key 값을 가중치 값으로 변경하고 부모를 추출된 정점에 할당합니다.

 

프림의 핵심은 트리 집합을 단계적으로 확장하는 것이고,

새로운 정점을 연결할 때마다 새로운 정점에서 갈 수 있는 아직 연결되지 않은 정점들에 대한 간선을 추가해줘야 합니다.

Priority Queue를 이용한 최소 힙으로 구현할 수 있고, 다익스트라 알고리즘과 구현 방식이 유사합니다.