Minimum Spanning Tree 최소 신장 트리
- Spanning Tree : 모든 정점을 연결하는 Tree (사이클이 없고, 최소한의 엣지만을 가지는 tree)
- MST : 신장 트리 중에서 엣지의 가중치 합이 최소가 되도록하는 트리
- 합이 최소가 되는 것은 1개가 아닐 수 있다!
- MST를 구성하는 모든 subset들도 MST이다!
-
Safe edge : 현재까지 선택된 간선들의 집합(A)에 어떤 간선을 추가해도 여전히 MST가 된다면 edge is safe for A라고 말한다.
-
MST의 Growing
- pseudocode
-
초기화 : A = empty
-
유지 : safe edge만 A에 추가 (while 조건은 **모든 정점을 다 돌았니?**에 대한 문장임)
-
종료 : 다 더한 후 A가 MST라면 종료한다. → A는 MST이자 신장 트리이다.
-
Cross cut / light edge
- edge (u,v)가 cut (S, V-S)을 가로지를 때, 그 가로지르는 엣지 중에 가장 가중치가 작은 엣지를 Light edge라고 한다.
- 가운데 중간 선을 기준이 cut(S, V-S)
-
Disjoint-Set Union Problem 서로소 집합 유니온 문제
- 서로소 집합이란? 교집합이 없는 집합들을 얘기한다.
- 다음의 작업을 해야함
- makeset은 각자의 집합을 만들어줌 (초기화)
- union은 병합하려는 집합 2개를 빼고 병합된 집합을 더하는 과정
- findset은 자신이 속한 집합을 리턴
-
Kruskal 알고리즘 (MST를 찾는 알고리즘)
- 엣지를 오름차순으로 정렬해서 정렬순서대로 합집합이 가능한지 확인하면서 MST를 찾는 방법
- 색깔이 다르면 집합이 다른 것임 (집합을 색으로 표현)
- 현재 Edge의 가중치 1→2→5→8까지 진행하여 집합을 이룬 모습이 다음과 같다.
- 모든 집합이 연결됨 → MST발견! 그 뒤는 안해도되는데 17, 19, 21, 25 그대로 진행해줌
- 최종 MST
- Kruskal 알고리즘 pseudocode
-
Prim’s 알고리즘 (MST를 찾는 알고리즘)
- 정점의 값(key)을 무한대로 초기화하고, Queue에 모든 정점을 집어넣고 Queue의 최솟값을 dequeue하면서 인접 리스트를 확인하며 인접한 정점과의 엣지 값을 정점의 key로 갱신하고 인접한 정점의 key보다 엣지 가중치가 더 작다면 갱신하는 방법
- 기존의 연결을 다른 연결로 갱신할 때, 기존 연결을 끊어주고 엣지 가중치도 갱신해줘야함
- 처음엔 다 무한대라 start vertex r을 지정해준다. → 0으로 만들어 최솟값 지정
- 3이 최소니까! 다음 u를 3으로!
-
기존 연결로 인한 정점의 값이 14였는데 새로운 연결로 인한 정점의 값이 10이기 때문에 더 작아서 10으로 갱신하고 기존 연결을 해제!
-
다음으로 큐에서 작은 값이 8이므로 8을 u로 선택!
- 앞선 논리와 똑같은 논리로 10 > 5이므로 갱신 + 기존 연결 끊어줌
- 이제부터는 모든 정점이 연결됨!
- 프림 알고리즘 완성! MST 발견!!!
-
- 정점의 값(key)을 무한대로 초기화하고, Queue에 모든 정점을 집어넣고 Queue의 최솟값을 dequeue하면서 인접 리스트를 확인하며 인접한 정점과의 엣지 값을 정점의 key로 갱신하고 인접한 정점의 key보다 엣지 가중치가 더 작다면 갱신하는 방법