[알고리즘] 크루스칼

이전 포스팅에서 union-find알고리즘을 살펴보았다.

union-find알고리즘은 무방향 그래프 내에서의 사이클을 판별할 때도 사용할 수 있는 특징이 있다.

신장트리란?

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.
이 조건은 트리의 성립 조건이기도 하다. 그래서 이러한 그래프를 신장 트리라고 부른 것이다.

 

크루스칼 알고리즘

가능한 한 최소한의 비용으로 신장 트리를 찾는 것을 최소 신장 트리 알고리즘이라고 한다.
최소 신장 트리 알고리즘 중 하나로는 크루스칼 알고리즘이 있다.

크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있는데, 이 알고리즘은 그리디 알고리즘으로 분류된다. 

 

 

크루스칼 알고리즘의 구현 방법

먼저 모든 간선에 대해 정렬을 수행한 뒤에 가장 거리가 짧은 간선부터 집합에 포함시키면 된다.
이때 사이클을 발생시키는 간선의 경우는 집합에 포함시키지 않는다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.

- 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.

- 사이클이 발생하는 경우 최소 신장 트리에 포함하지 않는다.

3. 모든 간선에 대하여 2번의 과정을 반복한다.

 

소스코드

 

시간 복잡도

크루스칼 알고리즘의 시간 복잡도는 O( ElogE)의 시간 복잡도를 가진다. 

가장 시간이 오래 걸리는 부분은 간선을 정렬하는 작업이다.