신장트리(스패닝 트리, Spanning Tree) 란?
그래프의 모든 정점이 간선으로 연결되어 있다.
그래프 아나에 사이클이 포함되어 있지 않다.
최소 신장트리(최소 스패닝 트리,Minimum Spanning Tree) 란?
최소 비용으로 만들어진 신장 트리, 가중치 합이 가장 작은 신장 트리
크루스칼 알고리즘
시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하여 MST를 구성하므로, 그 과정에서 사이클을 이루는지 항상 확인해야한다. 사이클 확인 방법으로는 Union-Find(Disjoint-Set) 방법이 있다.
시간 복잡도는 O(E logE)
관련 문제
leetcode 1202 Smallest String with swaps