[알고리즘] 크루스칼 알고리즘

크루스칼 알고리즘 🤯

🐍 크루스칼 알고리즘이란?

크루스칼 알고리즘은 사이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해나가며 최소 신장 트리를 만드는 알고리즘이다.


🐍 크루스칼 알고리즘의 동작

  1. 모든 간선을 가중치의 오름차순으로 정렬한다.
  2. 사이클을 형성하지 않는 선에서 간선을 선택한다.
    • 가장 낮은 가중치를 먼저 선택한다.
    • 사이클을 형성하면 그 간선은 버린다.


그림을 통해 살펴보자.

image

(b): 가장 작은 가중치를 가지는 5를 선택한다.

(c): 5를 제외한 가중치중 가장 작은 7을 선택한다.

(d): 남은 간선 중 가장 작은 가중치는 8인데 3개가 존재한다. 이 중 하나를 임의로 선택하면 된다.

(e): 위와 같이 가중치가 8인 간선이 두 개 존재하므로 하나를 임의로 선택한다.

(f): 남은 가중치가 8인 간선을 선택하면 사이클이 만들어지므로 가중치가 9인 간선을 선택한다.

(g): 마지막으로 가중치 11을 가진 간선을 선택하며 끝이 난다.


❗ 여기서 사이클이 생성되었는지 확인하기 위해 union-find 알고리즘을 사용한다.


🐍 union-find 란?

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


🐍 union-find 동작 구조

image

초기에 1, 2, 3, 4 노드는 각각 자기 자신으로 초기화 되어 있다.


image

(1, 2) 간선을 선택하면 2번 인덱스 배열의 값이 1로 바뀐다.


image

(1, 3) 간선을 선택하면 3번 인덱스 배열의 값도 1로 바뀐다.


이 상태에서 2와 3의 값이 모두 1이므로 둘을 연결하면 사이클이 생성된다.

이것으로 사이클의 생성 여부를 알 수 있다.


크루스칼 알고리즘 관련 문제 / 풀이