MST(Minimum Spanning Tree) : 최소 비용 신장 트리
- 신장 트리(Spanning Tree)
: 무방향 그래프 G(V, E)에서 E에 속한 간선들로 사이클을 포함하지 않으면서 모든 정점 V를 연결한 부분 그래프
* V : 정점의 개수 E : 간선의 개수
· 여러 신장 트리 중 간선들의 가중치 합이 최소인 신장 트리
크루스칼 알고리즘 (Kruskal Algorithm)
· 최소 신장 트리를 구하는 알고리즘
· 간선의 가중치의 합이 최솟값이 되도록 하는 알고리즘
크루스칼 알고리즘의 동작 방식
1. 그래프의 간선들을 가중치 기준 오름차순으로 정렬
2. 정렬된 간선 리스트에서 가중치가 가장 작은 간선을 선택하여, 정점들을 연결(Union)
3. 두 정점 사이의 간선이 연결되어 있다면 스킵(사이클 형성X)
4. 위 과정을 반복하여 최소 비용의 간선들만 이용하여 모든 정점을 연결
크루스칼 알고리즘의 시간 복잡도
- O(Elog E) ← 간선들을 가중치 순으로 정렬할 때 일반적인 퀵정렬 만큼의 시간이 소요
* 유니온-파인드(Union-Find) 알고리즘은 상수 시간 복잡도(O(1))를 가지기 때문에
간선을 정렬하는 로직(Quick Sort)이 전체 시간 복잡도를 좌우
크루스칼 알고리즘 동작
1. 그래프의 간선들을 가중치(거리) 기준 오름차순으로 정렬
2. 가장 작은 간선부터 정점들을 연결
3. 두 번째 간선 연결
4. 세 번째 간선 연결
5. 네 번째 간선 연결
6. 다섯 번째 간선 연결
7. 여섯 번째 간선 연결
이미 정점 1과 4가 부모 노드 1로 연결이 되어있기 때문에 스킵(사이클 형성X)
8. 일곱 번째 간선 연결
9. 이미 모든 정점이 이어졌기 때문에 뒤의 과정은 스킵
결과적으로 위와 같은 그래프가 만들어지고 총 비용은 12 + 13 + 17 + 20 + 24 + 37 = 123이 된다.
