[Data Structure] 최소 신장 트리(MST, Minimum Spanning Tree)

신장 트리(Spanning Tree)?

Spanning Tree는 그래프 내의 모든 정점을 연결하고 사이클이 없는 그래프이다.

• n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다.

 

특징

• DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다.
• 하나의 그래프에는 많은 신장트리가 존재할 수 있다.
• Spanning tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다.
• 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결한다.

 

최소 신장 트리(MST, Minimum Spanning Tree)?

최소 신장 트리는 각 간선의 가중치 합이 최소가 되는 신장 트리이다.

즉, 그래프에 있는 모든 정점들을 가장 적은 비용과 간선으로 연결하는 것이다.

 

특징

• 간선의 가중치 합이 최소여야 한다.
• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다.
• 사이클이 포함되어서는 안된다.

 

구현

MST 구현 방법에는 대표적으로 2가지가 있다.

 

크루스칼(Kruskal) 알고리즘

크루스칼 알고리즘은 그래프 내의 모든 간선의 가중치를 확인하고 가장 작은 가중치부터 확인(검증)해서 최소 신장 트리를 만드는 방법.

탐욕적인(greedy) 방법을 통해 구현할 수 있다.

 

크루스칼 알고리즘

[Algorithm] 크루스칼 알고리즘 (Kruskal Algorithm)

 

프림(Prim) 알고리즘

프림 알고리즘은 로버트 프림(Robert C. Prim)이 만든 것으로 최소 신장 트리에 연결된 정점 주변에 있는 간선의 가중치 중 가장 작은 것을 골라 최소 신장 트리를 만드는 알고리즘이다.

 

프림 알고리즘

[Algorithm] 프림 알고리즘(Prim's algorithm)