[자료구조] 최소 신장 트리 Minimum Spanning Tree

신장 트리란? (ST, Spanning Tree)

모든 임의의 정점이 연결된 그래프의 부분 그래프이다. 모든 정점이 간선으로 연결되어 있지만, 사이클은 존재하면 안된다.

 

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

그래프의 간선에 가중치가 부여될때, 신장 트리를 구성하는 간선들의 가중치의 합이 가장 작은 신장 트리이다. 이 최소 신장 트리를 구할때엔 보통 2가지 알고리즘을 활용해 최소 신장 트리를 구하게 되는데, 크루스칼 알고리즘과 프림 알고리즘이 그것이다. 

맨 위엔 사이클이 존재하는 그래프, 아래쪽 3개는 신장트리에 해당하고 강조된 가운데 트리가 최소 신장 트리다.

최소 신장 트리의 특징

- 신장 트리들 중 간선의 가중치 합이 최소이다.
- N개의 정점을 갖는 그래프에 대해 N-1개의 간선만 사용해야 한다.
- 사이클이 존재하면 안된다.
- 항상 최단 경로를 보장하지는 않는다.
  => (최단 경로를 구하려면 가중치가 없을땐 BFS, 가중치가 존재할땐 다익스트라 알고리즘을 통해 구해야한다.)