수학과의 좌충우돌 프로그래밍

Spanning Tree 란? Spanning Tree 란 스패닝 트리라고 읽으며 다른 말로 신장트리 라고도 합니다. 이는 그래프 내의 모든 정점을 포함하는 트리를 말합니다. 그래프의 일부 간선을 이용해 만든 트리로서 항상 그래프의 부분집합이 됩니다. Spanning Tree 의 특징 Spanning Tree 는 이름에서도 알 수 있듯이 트리 중 하나이기 때문에 트리의 특징은 모두 포함합니다. 하나의 그래프에는 여러 Spanning Tree 를 가질 수 있습니다. 모든 정점을 포함하고 사이클은 생기면 안되기 때문에 N 개의 노드에 대해서 정확하게 N-1 개의 엣지를 가지게 됩니다. MST 란? MST 란 Spanning Tree의 한 종류로서 사용되는 간선의 가중치 합이 최소인 트리를 말합니다. 이 때 ..