최소 스패닝 트리 (MST, Minimum Spanning Tree)

Spanning Tree 특징

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

• 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다.
• V개의 정점을 (V-1)개의 간선으로 연결되어야 한다.

 

MST(Minimum Spanning Tree)

Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리

1. Kruskal 알고리즘

 

2. Prim 알고리즘

시작 정점에서 부터 출발하여 스패닝 트리 집합을 단계적으로 확장

 

Prim 알고리즘의 동작 과정

1. 시작 정점을 힙에 저장
2. 방문하지 않은 정점중에서 가중치가 가장 낮은 정점을 선택
3. 위 과정을 트리가 (V-1)개의 간선을 가질 때 까지 반복

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

 

백준 1922