[그래프] MST 구현 알고리즘 - Kruskal Algorithm

MST란?

2021.03.13 - [Algorithm - 이론] - [그래프] 최소 신장 트리(MST, Minimum Spanning Tree)

Kruskal Algorithm

Kruskal Algorithm 은 간단히 말해 아래와 같다.

1. 그래프의 간선들을 가중치의 오름차순으로 정렬

2. 정렬된 간선 리스트를 앞에서부터 순서대로 탐색하면서, Cycle 을 형성하지 않는 경우만 선택함

3. 2에서 선택된 간선을 MST 의 집합에 추가함.

 

Cycle 판별하기

2번에서 선택된 간선이 Cycle 을 형성하는지 아닌지 판별하는 것이 핵심인데,

Cycle 이 형성되는지 아닌지는 'Union-Find 알고리즘' 을 이용한다.

• Union-Find 
  
  • Disjoint Set(서로소 집합)을 표현하는 자료구조
  • 서로 다른 두 집합을 병합하는 Union 연산, 집합 원소가 어떤 집합에 속해있는지를 찾는 Find 연산으로 이뤄짐

2021.04.20 - [Algorithm - 이론] - Union-Find 알고리즘

Union-Find 알고리즘

실제 문제 풀이를 통해 Kruskal Algorithm 을 구현해보자.

2021.03.13 - [Algorithm/Greedy] - [프로그래머스] 섬 연결하기

[프로그래머스] 섬 연결하기

 

References

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

https://chanhuiseok.github.io/posts/algo-33/