[알고리즘] 크루스칼 알고리즘(Kruscal Algorithm)

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 그리디 알고리즘(Greedy Algorithm)의 일종이다.

크루스칼 알고리즘은 가중치가 가장 작은 간선으로부터 시작한다.

 

위에서 보았던 연결 그래프를 예시로 크루스칼 알고리즘의 과정을 보자.

우선 간선을 가중치 오름차순 순으로 정렬시킨다.

1-2 간선부터 선택을 한다.

다음으로 2-4 간선을 선택한다.

다음으로는 1-4 간선이다.

하지만 1-4 간선을 연결하게 되면 사이클이 이루어진다.

따라서 이 간선은 건너뛴다.

 

다음으로는 1-3 간선을 선택한다.

3-4를 선택하면 사이클이 되므로 종료한다.

사이클 판단하기: Union-Find

위의 과정을 보면, 사이클이 발생해 패스했던 부분이 있다.

이를 구현할 때 사용하는 거이 Union-Find 자료구조이다.

• 상호 배타적 집합(disjoint-set)이라고도 한다.
• 여러 노드 중 두 개의 노드가 현재 같은 그래프에 속하는지 판별한다.
• Uion: a와 b가 포함되어 있는 집합을 합치는 연산
• Find: a 또는 b가 어떤 집합에 포함되어 있는지 찾는 연산

위 사진에서 오른쪽 표는 각 노드 별 부모 노드를 나타내는 표이다.

아까와 같이 한번 더 가중치 순으로 선택할 것이다.

이 때, 1, 2번 노드는 같은 집합이고, 서로의 부모 노드가 다르므로  Union 연산에 의해 합쳐진다.

부모를 합칠 때는 일반적으로 더 작은 값쪽으로 합친다.

따라서 2번의 부모는 1번이 된다.

 

이어서 2-4번 간선을 선택한다.

2와 4는 서로 다른 부모 노드를 가지고 있으므로 Union 연산에 의해 합쳐진다.

이 때 4의 루트 노드는 2가 되어야하지만, 2의 루트 노드는 1이다.

이를 재귀를 통해 확인한다.

즉, 4번 노드의 부모 노드는 1이 된다.

 

다음으로 1-4 간선을 선택한다.

이 때 1번과 4번 노드의 부모 노드가 같은 것을 확인할 수 있다.

따라서 사이클을 만들지 않기 위해 Union 연산을 하지 않는다.