그래프에서 최소비용 문제는 크게 2종류이다
- 모든 정점을 연결하면서 가중치 합 최소인 트리
- 두 정점 사이 최소비용 (최단경로)
신장트리란?
- n개 정점 무향그래프에서, n개 정점과 n-1개 간선으로 이루어진 트리.
- cycle 없음.
최소신장트리 = Minimum Spanning Tree = MST
- 무향 가중치 그래프에서, 신장트리를 구성하는 간선들의 가중치 합이 최소인 신장트리
완전탐색으로 MST를 찾을 수 있을까?
- 조합으로 가능
- nCr에서, 정점이 V이고 간선이 E라고 하면, 신장트리 조건을 만족하기위해 v-1개 간선을 사용해야 한다.
- 그러므로 e C v-1 인데, 30C15만 돼도 1억5천만 인데다가, 최소값 갱신도 계속해줘야하므로, 대부분의 경우 완탐은 부적절
MST찾는 알고리즘 3개 : Kruskal, Prim, Djikstra
- 참고로 셋 다 그리디임. 그리디 ⊃ Kruskal, Prim, Djikstra
1. KRUSKAL
- 원리 : 간선을 오름차순 정렬한 뒤 가중치 낮은 것부터 하나씩 선택, n-1개 선택하면 종료
- 단, 사이클 존재하면 남은 것 중 그 다음 가중치 낮은 것을 선택
- KRUSKAL의 시간복잡도
- union-find는 애커만 역함수에 의해 거의 O(1)이므로.
- 오름차순 정렬하는 시간이 알고리즘 시간의 대부분을 차지함. - 그러므로 간선이 너무 많으면 KRUSKAL이 적합하지 않을 수 있다. - 짜기 쉬우니까 비슷하면 KRUSKAL ㄱ
2. PRIM
- 원리 :
- 임의의 정점 하나를 MST 집합에 포함시키고 시작
- 현재 MST 집합에서 연결 가능한 간선 중 가중치가 가장 작은 간선을 선택
- 단, 선택한 간선의 반대쪽 정점이 이미 MST 집합에 있으면 스킵 (사이클 방지)
- n-1개 간선이 선택될 때까지 반복
- PRIM의 시간 복잡도
- 우선순위 큐 사용 시 : O(E log V)
- 우선순위 큐 없이 배열로 구현 시 : O(V²) → 정점이 많고 간선이 적을 때 유리
- 간선이 많은 밀집 그래프에서 Kruskal보다 유리할 수 있음 (정렬 비용 없음)
3. DIJKSTRA
- 원리 :
- Prim과 구조가 거의 같지만 목적이 다름 — MST가 아니라 최단 경로 탐색
- 시작 정점에서 dist[] 배열을 관리, 아직 확정되지 않은 정점 중 dist가 가장 작은 것을 선택
- 선택된 정점의 인접 정점들에 대해
dist[u] + w < dist[v]이면 갱신 (relaxation) - 모든 정점이 확정될 때까지 반복
- DIJKSTRA의 시간 복잡도
- 우선순위 큐 사용 시 : O(E log V)
- 우선순위 큐 없이 배열로 구현 시 : O(V²)