minimum spanning tree (1) 썸네일형 리스트형 125. Minimum Spanning Tree 무향 연결 그래프의 스패닝 트리(신장 트리, Spanning Tree)는 그래프의 모든 정점을 포함하는 트리이다. 쉽게 말해서 그래프에서 (그래프가 분리되지 않도록) 간선들을 제거해서 트리 구조가 남았을 때 이를 스패닝 트리라고 한다. 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있다. 간선에 가중치가 있는 그래프는 스패닝 트리에 포함되는 간선의 가중치의 합이 다양하게 나올 수 있는데, 이중 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리(최소 신장 트리, Minimum Spanning Tree, MST)라고 한다. 이 최소 스패닝 트리가 꽤 다양한 곳에서 사용되므로 알아 두면 좋다. 무향 연결 그래프에서 최소 스패닝 트리를 구하는 방법은 여러 가지가 있는데, 이 블로그에서는 세 가지를 .. 이전 1 다음
