Spanning Tree 스패닝 트리란 그래프 내 모든 정점을 포함하는 트리입니다. 또한, 사이클을 포함하면 안된다는 특징이 있습니다. MST(Minimum Spanning Tree) 최소 스패닝 트리(최소 신장 트리)는 스패닝 트리 중 사용된 간선의 가중치가 최소인 트리를 뜻합니다. MST 특징 N개의 정점에 대해 N-1개의 간선이 존재합니다. 스패닝 트리이므로 사이클을 포함해서는 안됩니다. 간선 가중치의 합이 최소여야합니다. MST 구현 방법 1. Kruskal 알고리즘 Greedy method를 활용하여 구현합니다. 간선을 가중치 기준으로 오름차순 정렬합니다. 사이클을 포함하지 않는 경우 MST 구성 간선으로 포함시킵니다. N개의 정점에 대해 N-1개의 간선을 포함시킬 때까지 반복합니다. 💻 Kru..