최근 수정:
Minumum Spanning Tree.
최소 스패닝 트리. 최소 신장 트리라고도 한다.
스패닝 트리 중에서 선택한 간선들의 가중치 합이 최소가 되는 트리.
그래프에서 간선들을 적당히 선택하여 스패닝 트리를 생성하는데, 가중치 합이 최소가 되어야 한다. 이때 사용하는 알고리즘은 크게 두 가지.
1. 아무 정점이나 선택하여 MST에 넣음.
2. MST에서 연결된 간선 중에 최소 가중치의 간선을 선택.
3. 선택한 가중치의 간선을 MST에 연결.
4. 모든 정점을 방문하지 않았다면 2번으로 이동. (루프)
간단하게 간선의 가중치를 우선순위 큐로 사용하는 BFS라고 생각하면 된다. 단, 사이클이 없어야 하므로 방문한 정점은 다시 방문하지 않도록 해야 한다.
시간 복잡도: O(E logV). E는 간선의 수, V는 정점의 수.
1. 간선의 가중치가 작은 간선부터 탐색.
2. MST에 연결했을 때 사이클이 생기지 않으면 MST에 추가.
3. 생긴다면 다음 간선 탐색.
말로 하면 굉장히 간단하다. 간선들을 가중치를 기준으로 정렬해 놓고 작은 간선부터 하나씩 연결하면서 사이클이 생기지 않도록 연결하면 된다.
하지만 실제 구현은...생각보다 조금 복잡하다. 사이클이 생기지 않도록 연결할 때가 중요한데, 이는 Disjoint-set으로 구현해야 한다.
시간 복잡도: O(E logE). E는 간선의 수.
시간 복잡도는 비슷하지만, logV < logE 인 경우는 프림이 낫다. (그래프가 dense한 경우)