[Algorithm]Minimum Spanning Trees

신장 트리(Spanning Tree)란?

모든 임의의 정점이 연결된 그래프인 연결 그래프의 부분 그래프다. 모든 정점이 간선으로 연결되어 있지만 사이클이 존재하지 않은 그래프다.

Minimum Spanning Tree(MST) 최소신장트리란?

무방향 연결 그래프에서 모든 정점을 연결하면서 간선의 가중치 합이 최소인 트리

Spanning Tree는 모든 정점이 연결되어 있으면서 사이클이 없는 부분 그래프이고, 그 중 가장 가중치 합이 적은 것이 MST이다.

MST의 특징

• 신장 트리들 중 간선의 가중치 합이 최소이다.
• n개의 정점을 갖는 그래프에 대해 n - 1 개의 간선만을 사용해야 한다.
• 사이클이 존재해서는 안된다.
• 최소 신장 트리는 최단 경로를 보장하지 않는다.

MST 알고리즘

(1) Kruskal's Algorithm

간선을 가중치 기준 오름차순으로 정렬

사이클이 생기지 않도록 하나씩 선택 (Union-Find 사용)

동작 과정

1. 모든 간선을 가중치 기준으로 정렬

2. 하나씩 꺼내며 두 정점이 연결되어 있지 않으면 선택

3. V-1개의 간선을 선택하면 종료

⏱️ 시간복잡도

O(E log E) (E는 간선의 수) — 정렬 + Union-Find

(2) Prim's Algorithm

정점을 하나씩 확장하며 최소 간선 선택 (Priority Queue 사용 가능)

동작 과정

1. 임의의 정점에서 시작

2. 연결된 간선 중 최소 가중치를 가지는 간선 선택

3. 새로운 정점을 방문하고, 이 정점과 연결된 간선 추가

4. 모든 정점이 연결될 때까지 반복

⏱️ 시간복잡도
O(E log V) (V는 정점의 수)