125. Minimum Spanning Tree

무향 연결 그래프의 스패닝 트리(신장 트리, Spanning Tree)는 그래프의 모든 정점을 포함하는 트리이다. 쉽게 말해서 그래프에서 (그래프가 분리되지 않도록) 간선들을 제거해서 트리 구조가 남았을 때 이를 스패닝 트리라고 한다. 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있다.

 

간선에 가중치가 있는 그래프는 스패닝 트리에 포함되는 간선의 가중치의 합이 다양하게 나올 수 있는데, 이중 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리(최소 신장 트리, Minimum Spanning Tree, MST)라고 한다. 이 최소 스패닝 트리가 꽤 다양한 곳에서 사용되므로 알아 두면 좋다.

정점이 9개인 그래프의 MST 중 하나

무향 연결 그래프에서 최소 스패닝 트리를 구하는 방법은 여러 가지가 있는데, 이 블로그에서는 세 가지를 소개한다. 유향 그래프의 스패닝 트리는 여기서는 다루지 않는다.

 

→ solved.ac tag: mst