[Kruskal Algorithm] 크루스칼 알고리즘(feat. Union-find)

크루스칼 알고리즘을 이해하기 위해서는 신장트리, 최소 신장트리에 대한 개념을 먼저 이해해야 한다.

신장트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.

* 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다.

 

이렇게 서로 사이클이 발생하지 않고 모든 정점을 잇는 경로를 신장트리라고 한다.

그럼 최소신장트리(MST)란 무엇일까?

최소 신장 트리(MST)란 최소한의 비용으로 구성되는 신장 트리를 말한다.

이처럼 간선에 대한 가중치가 주어졌을 때 최소한의 가중치를 가지고 모든 정점을 잇는 트리이다.

 

 

이제 크루스칼 알고리즘에 대해 알아보겠다

크루스칼 알고리즘이란 MST를 구하는 방식 중 하나로 간선의 가중치의 합이 최솟값이 되도록

모든 노드를 연결시킨다.

 

크루스칼 알고리즘 동작 과정

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.
   1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시킨다.
   2. 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않는다
3. 모든 간선에 대하여 2번의 과정을 반복한다.

이처럼 오름차순으로 정렬을 하면 아래와 같이 가중치 기준으로 오름차순으로 정렬된다.

(3,4) 7 | (4,7) 13 | (4,6) 23 | (6,7) 25 | (1,2) 29 | (2,6) 34 | (2,3) 35 | (5,6) 53 | (1,5) 75 

 

이 과정에서 Union find의 개념을 이용해야 한다. 그 이유는 무엇일까?

 

그 이유는 바로 사이클이 생기는 것을 방지하기 위해서이다.

Union-find의 개념을 잘 모른다면 아래 글을 참조하길 바란다.

[Union Find, Disjoint Set] 유니온 파인드 함수 구현 방법(재귀 사용!)

 

Union-find의 개념을 이용해서 각 정점이 연결될 때 마다 두 정점을 Union 해서 부모노드를 같게 만든 뒤 두 정점이 연결되있다고 표시를 하는 것이다. 

 

수행조건

이렇게 반복해서 정점이 연결될 때 마다 Union을 하면 오름차순 순서대로 최소 가중치를 선택할 때 find를 이용하여 두 부모노드의 정점이 같은지 비교를 하고 만약 같다면 두 정점을 연결 하게되면 사이클이 형성되기 때문에(조건 x) continue를 하고 다음 최소 가중치를 비교해서 선택을 해야한다.

 

종료조건

두 정점이 연결될 때 마다 연결된 간선 수를 체크하는 변수(int check)를 하나 선언해주고 

만약 check == V(기존 정점 수)-1 이면 모든 정점이 연결되었으므로 종료한다.

 

MST를 이용할 수 있는 문제 ↓

1197번: 최소 스패닝 트리