크루스칼 알고리즘(Kruskals’ Algorithm)

date

May 6, 2023

slug

mst-kruskal

author

status

Public

category

💡 Algorithm

tags

MST(최소 스패닝 트리)

그래프

summary

간선이 적으면 크루스칼, 비용이 적은 간선부터 그리디하게

type

Post

thumbnail

Spanning Tree 신장트리

• Spanning Tree = 신장트리 = 스패닝트리

• 최소 연결 = 간선의 수가 가장 적다
• n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 Spanning Tree이다

Spanning Tree 특징

• DFS, BFS를 이용하여 구할 수 있다
• 탐색 도중에 사용된 간선만 모으면 됨

• 하나의 그래프에 여러 개의 스패닝 트리가 존재할 수 있음

• 스패닝트리는 모든 정점이 연결되어 있어야 하고 사이클이 있어선 안된다

MST 최소신장트리

MST 특징

• 간선의 가중치 합이 최소여야 함

• n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 함

• 사이클이 있으면 안됨

• 최단 경로를 보장하지는 않음

사용 문제 유형

• 도로, 통신 등 모든 노드를 방문해야 하는 문제 중 구축 비용이나 소요 시간 등을 최소로 해야 하는 문제

구현 알고리즘 2가지

• Kruskal 크루스칼 알고리즘

• Prim 프림 알고리즘

Kruskal’s Algorithm 크루스칼 알고리즘

• 간선 선택을 기반으로 한 알고리즘

• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택

• Kruskal은 그리디 알고리즘을 사용하지만 최적의 해답을 주는 것으로 이미 증명되어 있음

알고리즘 과정

1. 그래프의 간선들을 가중치의 오름차순으로 정렬(비용 낮은 순)

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
1. 즉, 현재 선택된 간선들과 사이클을 형성하지 않으면서 비용이 가장 낮은 가중치의 간선을 선택

3. 해당 간선을 MST의 집합에 추가

4. 선택된 간선의 개수가 (n-1)개가 될 때까지 2~3 반복

Cycle 여부 확인 ⇒ Union & Find

• Disjoint Set (서로소 집합)을 표현하는 자료구조

• 서로 다른 두 집합을 병합하는 Union 연산과, 집합 원소가 어떤 집합에 속해 있는지 찾는 Find 연산을 지원하기 때문에 Union & Find 라고 부름

시간복잡도 : O(E * logE)

• 거의 대부분의 시간이 간선들을 가중치 기준으로 정렬하는 데에 걸리는 시간 O(E logE)

• union-find : 상수

Simulation

1. 가장 작은 가중치의 간선인 BC 간선에서 시작

1. 그 다음으로 가장 가중치가 작은 DE 간선 선택

1. AC, CD, DF 간선의 가중치가 모두 동일하고 3개의 간선 모두 현재 선택된 간선들과 사이클을 이루지는 않으니 AC 간선을 MST 집합에 추가

1. 반복