[알고리즘] 최소 스패닝 트리

Minimum Spanning Tree

• 가중 그래프의 총 간선 무게가 최소인 신장 트리
• 신장 트리: 그래프의 모든 정점을 포함하는 부그래프 중 트리인 것

Prim-Jarnik MST

임의의 정점 S에서 시작하여 정점에 연결된 간선들 중 최소 가중치의 간선을 선택해 나가며 트리를 키워 나간다.

• 탐욕법
• 우선순위 큐를 사용한다.
• 새로 추가하려는 정점이 이미 트리에 속한 점이라면 무시한다. (싸이클 생성)
• 모든 정점이 트리에 포함되면 알고리즘을 중단한다.

Kruskal MST

간선들을 비용에 대한 오름차순으로 순회하면서 각 간선의 싸이클 발생 여부에 따라 트리에 간선을 추가해 나간다.

• 탐욕법
• Union-Find 알고리즘을 사용한다.
• 모든 간선에 대한 순회가 끝날 때까지 알고리즘을 반복한다.