최소 신장 트리(MST)

신장 트리 (Spanning Tree)

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

최소 신장 트리 (Minimum Spanning Tree)

무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

그래프에서 최소 비용 문제

KRUSKAL 알고리즘

# Union-Find 알고리즘

가중치가 작은 간선을 차례대로 선택하여 MST를 구성하는 알고리즘

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2. 가중치가 가장 낮은 간선부터 하나씩 확인
   1. 해당 간선이 연결하는 두 정점의 대표자가 다르다면 → 사이클이 생기지 않으므로 MST 집합에 추가
   2. 두 정점의 대표자가 같다면 → 사이클이 생기므로 간선을 무시
3. 모든 정점이 연결될 때까지 위 과정을 반복

PRIM 알고리즘

# Priority queue

하나의 정점에서 시작하여, 연결된 간선 중 가장 작은 가중치를 가진 간선을 선택해 나가며 MST를 만들어가는 알고리즘

1. 임의의 정점을 선택하여 시작
2. 선택된 정점에서 나가는 간선들을 우선순위 큐에 넣고, 가장 가중치가 작은 간선을 선택
3. 선택한 간선이 연결하는 정점이 아직 방문하지 않은 정점이라면 → 그 간선을 MST에 추가하고 해당 정점을 방문 처리
4. 새로 방문한 정점에서 나가는 간선들을 다시 우선순위 큐에 추가
5. 우선순위 큐가 빌 때까지 반복