spanning tree

[Algorithm] Spanning Tree와 MST (Minimum Spanning Tree)

Idea Spanning Tree Spanning tree는 그래프 내의 모든 정점을 포함하는 트리를 의미합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. 이때 간선의 개수가 최소이어야 하며, 따라서 최소 연결 부분 그래프라고도 합니다. N개의 정점에 대해서 모든 정점을 포함하는 트리를 만들기위해서는 최소 N-1개의 간선이 필요합니다. 따라서 Spanning Tree는 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결합니다. 이때 사이클을 포함해서는 안됩니다. MST (Minimum Spanning Tree) MST는 한 그래프에 대한 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미합니다. 그림에서 아래 3개의 신장 트리 중에서 ..