[알고리즘] 최소 비용 신장 트리(MST) - 크루스칼 알고리즘(Kruskal Algorithm)

신장 트리 (Spanning Tree)

신장 트리란 그래프안에서 모든 정점(노드)을 포함하는 트리이다. 

신장 트리는 모든 정점들이 연결되어 있어야 하고, 사이클을 포함하면 안된다. (사이클: 그래프가 순환되어 돌아오는 경로)

신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간선으로 연결하게 된다.

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

---

최소 비용 신장 트리 MST (Minimun Spanning Tree)

신장 트리들 중에서 사용된 간선의 가중치 합이 최소인 트리를 말한다.

크루스칼(Kruskal) 알고리즘과 프림 알고리즘이 있다.

출처: https://ghkvud2.tistory.com/97

---

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

그리디 알고리즘을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하여 최적의 답을 구하는 알고리즘이다.

크루스칼 알고리즘 동작

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
3. 해당 간선을 현재의 MST집합에 추가한다.

사이클 생성 여부 확인 방법

union-find 알고리즘 이용

합집합 찾기 알고리즘이라 하며, 서로소 집합(Disjoint-Set) 알고리즘 이라고도 부른다.

여러개의 노드가 존재할 때 두 개의 노드를 선택해서, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘.