[자료구조] 최소 신장 트리 - 크루스칼/프림 알고리즘

🎄신장 트리 (스패닝 트리)

최소 신장 트리에서 '신장 트리' 즉, 스패닝 트리는 노드 간의 경로가 오직 하나뿐인 트리를 말한다.

그래프 내의 모든 정점을 포함하며, 그래프의 최소 연결 부분 그래프라고 볼 수 있다.

 

최소 연결이란 간선의 수가 가장 적다는 뜻으로, n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이다.

따라서, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되며, 이것이 바로 스패닝 트리가 된다.

 

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

https://terms.naver.com/entry.naver?docId=3579408&cid=59086&categoryId=59093

하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 최소 신장 트리는 이러한 신장 트리중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다.

 

즉, 가중치를 간선에 할당한 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이 최소 신장 트리인 것이다.

또한, 최소 신장 트리 내에는 사이클이 포함되어선 안된다는 규칙을 잘 기억해야 한다.

 

가중치 합이 최소인 트리를 만들때, 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다. 

따라서, 이런 최소 신장 트리를 만들기 위한 알고리즘으로 크루스칼(Kruskal) 알고리즘과, 프림(Prim) 알고리즘이 있다.

 

✏️ 크루스칼 알고리즘

크루스칼 알고리즘은 그리디(Greedy)를 이용하여 모든 정점을 최소 비용으로 연결하는 최적의 해답을 구하는 알고리즘이다.

 

MST의 규칙에 의거하여 크루스칼 알고리즘의 각 단계에서 사이클을 이루지 않는 최소 비용의 간선을 선택하는 방식으로 이루어진다.

여기서 프림 알고리즘과 다른 핵심은 "간선 선택"을 기반으로 단계를 수행한다는 것이다.

이전 단계에서 만들어지는 신장 트리와는 상관없이 무조건 최소 비용의 간선만을 선택하면 된다.

 

[ 알고리즘 단계 ]

1. 그래프의 간선을 오름차순 정렬 한다.
2. 정렬된 간선 리스트의 첫번째부터 간선을 선택하고, 사이클을 형성하지 않는지 검사한다.
2-1. 이때, 사이클의 형성 여부를 확인하기 위해선 'union-find 알고리즘'을 사용한다.
3. 사이클을 형성하지 않는다면, 해당 간선을 MST 집합에 추가한다.

 

✏️ 프림 알고리즘

프림 알고리즘은 시작 정점에서 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법이다. 

 

크루스칼과 달리 "정점 선택"을 기반으로 단계를 수행하며, 이전 단계에서 만들어지 신장 트리를 확장해나가는 방법이다.

 

프림 알고리즘은 우선순위 큐를 사용해 구현할 수 있고, 프림 알고리즘도 그리디 패러다임에 속하므로 귀류법으로 증명할수도 있다.

 

귀류법?

귀류법 : 어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을, 즉 처음의 명제가 거짓임을 증명하는 방법

 

[ 알고리즘 단계 ]

1. 시작 정점이 MST 집합에 추가된다.
2. 앞 단계에서 만들어진 MST 집합에 연결된 정점 중에서, 최소 비용 간선으로 연결된 정점을 선택하여 트리를 확장한다. 
3. 위의 과정을 트리가 (N-1)개의 간선을 가질 때까지 반복한다.

 

각 정점들과 연결된 간선 중, 최소인 간선을 선택할 때 우선순위 큐를 사용하면 되고, 이미 방문한 정점들에 대한 visit 정보를 기록하여 구현한다.

---

참조

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

https://4legs-study.tistory.com/112

최소 스패닝 트리 (MST) : 프림 알고리즘 (Prim Algorithm)