최소 비용 신장 트리 알고리즘 간략 정리

목차

1. 신장 트리(Spanning Tree)
2. Kruskal 알고리즘
3. Prim 알고리즘

 

1. 신장 트리(Spanning Tree)

신장 트리는 그래프 내 정점이 최소의 간선으로 모든 정점이 연결되어 있는 트리로, 사이클이 없는 그래프입니다.

신장 트리에 n 개의 정점이 있다면, 항상 n-1 개의 간선이 존재합니다.

 

최소 비용 신장 트리는 간선들의 비용 합이 최소가 되는 신장 트리를 뜻합니다.

대표적인 알고리듬으로는 Kruskal 알고리듬과 Prim 알고리듬이 있습니다.

 

https://subscription.packtpub.com/book/application_development/9781785884504/7/ch07lvl1sec46/spanning-tree

 

2. Kruskal 알고리듬

전체 간선 중 비용이 낮은 간선을 우선적으로 선택해서 모든 정점을 사이클이 없도록 연결하는 방법으로, 간선의 수가 적을 때 적합합니다.

https://commons.wikimedia.org/wiki/File:MST_kruskal_en.gif

 

3. Prim 알고리듬

Kruskal과 달리, 시작 정점으로부터 인접한 간선 중 최소 비용의 간선을 선택하면서 모든 정점들을 이어나가는 알고리듬으로, 간선의 수가 많을 때 적합합니다.

 

https://kjaer.io/algorithms/