[자료구조/알고리즘 이론] MST(최소 신장 트리), Kruskal's/Prim's Algorithm

신장 트리(Spanning Tree)

https://www.geeksforgeeks.org/spanning-tree/

신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 연결하는 트리입니다.

 

신장 트리의 속성

- N개의 정점이 있는 그래프의 경우 해당 그래프에 대한 신장 트리의 간선 개수는 N-1개입니다.

- 연결이 끊어진 그래프에는 신장 트리가 없습니다.

- 신장 트리에는 순환이 없습니다. 하나의 정점에서 출발하여 해당 정점으로 다시 이어지는 간선이 존재한다면 신장 트리가 아닙니다.

 

최소 신장 트리(MST, Minimum Spanning Tree)

https://www.geeksforgeeks.org/spanning-tree/

그래프 내에 존재하는 Spanning Tree 중 사용 간선들의 가중치 합이 최소가 되는 트리를 MST(Minimum Spanning Tree), 최소 신장 트리라고 합니다.

 

최소 신장 트리의 속성

- N개로 이루어진 그래프라면 반드시 N-1개의 간선으로 구성됩니다.

- 총 간선 가중치의 합을 최소화하는 데에는 적합하지만 고유한 결과를 보장하지는 않습니다.

- 신장 트리와 마찬가지로 최소 신장 트리 또한 사이클이 포함되어서는 안됩니다.

 

그래프에서 최소 신장 트리를 찾기 위해 사용되는 알고리즘은 크게 두 가지 알고리즘이 있습니다.

 

Kruskal's Algorithm(크루스칼 알고리즘)

그래프의 순환을 피하기 위해 탐욕 알고리즘(greedy algorithm)을 사용하여 그래프의 모든 정점을 최소 비용(가중치)으로 연결하는 MST를 구하는 알고리즘입니다. O(E log E)나 O(E log V)의 시간복잡도를 가집니다.

 

알고리즘 과정

1. 모든 간선을 가중치를 기준으로 오름차순 정렬합니다.

2. 정렬순대로 그래프에 포함시킵니다.

3. 만약 선택한 간선이 사이클을 형성한다면 그래프에 포함하지 않습니다.

- 선택한 간선의 사이클 형성 여부 확인을 위해서 유니온 파인드(Union Find) 알고리즘을 사용합니다.

4. 그래프의 정점의 개수가 N개라고 할 때, 간선의 개수가 N-1개가 될 때까지 간선 탐색을 반복합니다.

 

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

위와 같은 그래프가 있다고 가정할 때, 간선을 가중치 기준 오름차순 정렬하면 아래와 같습니다.

정점1	정점2	가중치
6	7	1
2	8	2
5	6	2
0	1	4
2	5	4
6	8	6
2	3	7
7	8	7
0	7	8
1	2	8
3	4	9
4	5	10
1	7	11
3	5	14

 

가중치 순으로 그래프에 포함시키는 과정을 반복합니다.

 

가중치 1을 가지는 (6, 7) 간선을 포함합니다. (간선 1개)

가중치 2를 가지는 (2, 8) 간선을 포함합니다. (간선 2개)

가중치 2를 가지는 (5, 6) 간선을 포함합니다. (간선 3개)

가중치 4를 가지는 (0, 1) 간선을 포함합니다. (간선 4개)

가중치 4를 가지는 (2, 5) 간선을 포함합니다. (간선 5개)

가중치 6을 가지는 (6, 8) 간선을 포함할 경우, 사이클이 발생함으로 포함하지 않습니다. (간선 5개)

가중치 7을 가지는 (2, 3) 간선을 포함합니다. (간선 6개)

가중치 7을 가지는 (7, 8) 간선을 포함할 경우, 사이클이 발생함으로 포함하지 않습니다. (간선 6개)

가중치 8을 가지는 (0, 7) 간선을 포함합니다. (간선 7개)

가중치 8을 가지는 (1, 2) 간선을 포함할 경우, 사이클이 발생함으로 포함하지 않습니다. (간선 7개)

가중치 9를 가지는 (3, 4) 간선을 포함합니다. (간선 8개)

 

그래프의 정점 개수가 N개일 때, 간선의 개수가 N-1개가 되면 종료합니다.

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

 

Prim's Algorithm(프림 알고리즘)

크루스칼 알고리즘과 다르게 최소 비용(가중치)의 간선을 시작 간선으로 선택한 후, 인접 간선들 중 가중치의 합이 최소가 되는 간선을 선택하여 MST를 단계적으로 확장하는 알고리즘입니다. 인접행렬을 사용할 경우 O(V^2)의 시간복잡도, 이진 힙을 사용할 경우 O(E log V)의 시간복잡도를 가집니다.

 

알고리즘 과정

1. 최소 가중치를 가지는 간선을 시작 간선으로 선택합니다.

2. 현재 연결되지 않은 정점과 이어지는 간선들 중 최소의 가중치를 가지는 간선을 선택하여 그래프를 확장합니다.

3. 그래프의 정점의 개수가 N개일 때, 간선의 개수가 N-1개가 될 때까지 위의 과정을 반복합니다.

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

위의 그래프에 프림 알고리즘을 적용해 봅시다.

 

가장 작은 가중치를 가지는 (6, 7)을 시작 간선으로 선택합니다.

정점 6, 정점 7과 연결된 간선 중 가중치가 가장 적은 간선은 가중치가 2인 (5, 6) 간선입니다. 그래프를 확장합니다.

정점 5, 정점 6, 정점 7과 연결된 간선 중 가중치가 가장 적은 간선은 가중치가 4인 (2, 5) 간선입니다. 그래프를 확장합니다.

위의 과정을 반복할 경우 MST의 결과는 아래와 같습니다.

https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/?ref=header_search

 

앞서 언급했던 것처럼 그래프 내의 최소 신장 트리는 여러 개일 수 있습니다. 위의 결과는 다수의 예시 중 하나일 수 있으며 다른 형태의 MST가 나올 수도 있습니다.

 

최소신장트리를 코드로 구현하는 것을 연습하기 위해서 아래의 문제를 푸는 것을 추천합니다.

https://www.acmicpc.net/problem/1197

 

References

https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/

https://www.geeksforgeeks.org/spanning-tree/

https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/?ref=header_search

https://www.youtube.com/watch?v=4ZlRH0eK-qQ&list=LL&index=2&ab_channel=AbdulBari

https://blog.naver.com/ndb796/221230994142