📌 최소비용 신장트리(MST, Minimum Spanning Tree)란?
- 신장 트리(ST, Spanning Tree)는 사이클 없이 모든 노드를 연결하는 트리입니다.
- 모든 정점을 포함한다.
- 정점간 서로 연결되면서 사이클이 존재하지 않는 그래프이다.
- 그래프에 여러 개의 신장 트리가 존재할 수 있는데, 이 중 간선의 가중치 합이 최소인 것을 최소비용 신장트리(MST)라 합니다.
📌 Kruskal 알고리즘이란?
Kruskal 알고리즘은 최소비용 신장트리(이하 MST)를 찾는 대표적인 알고리즘입니다.
MST를 구하는 알고리즘으로 Prim 알고리즘도 있는데, Prim은 정점을 기준으로 한다면, Kruskal은 간선을 기준으로 합니다.
아래와 같은 그래프에서 MST를 찾아보겠습니다.
가장 적은 비용으로 연결만 시키면 되기 때문에 간선의 가중치를 기준으로 가중치가 적은 것부터 하나씩 그래프에 포함시켜나가면 됩니다.
먼저, 위 그래프에서 간선을 오름차순으로 정렬하면 다음과 같습니다.
그럼 위 테이블을 참고해 가중치가 적은 간선부터 하나씩 그래프에 추가해보겠습니다.
그래프에서 간선을 하나씩 추가해나가다가 사이클이 형성되는 (1, 3) 간선을 만나면 그리지않고 넘어갑니다.
그럼 간선을 추가했을 때 사이클이 형성되는지는 알기위해 Disjoint-Set 자료구조 사용
최종적인 MST는 다음과 같습니다.
Reference
꿈꿈