[그래프 알고리즘] 크루스칼 알고리즘 Kruskal Algorithm

그래프 알고리즘이란, 그래프와 같은 복잡하고 연결성이 높은 자료구조에서
순회 (Graph Traversal), 탐색 및 검색 (Graph Search) 등과 같은 목적으로 사용되는 알고리즘이다.

 

신장 트리란, 그래프 내의 모든 정점을 포함하는 트리로, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다.

 

 

최소 신장 트리 알고리즘이란,

최소 신장 트리란 그래프 내의 여러 신장 트리 중 가중치가 최소가 되는 신장 트리를 말하며, 최소 신장 트리 알고리즘은 그래프 내의 최소 신장 트리를 찾는 알고리즘이다.

각 엣지에 가중치가 부여된 무방향 그래프에서 만들어지는 신장 트리중 가중치의 합이 가장 작은 신장 트리를 특별히 최소 비용 신장 트리(minimum cost spanning tree)라고 한다. 이는 통신 네트워크나 빠른 길찾기 등의 문제에서 많이 활용되고 있다.

최소 신장 트리 알고리즘에는 2가지 알고리즘이 대표적이다.

•  크루스칼 알고리즘 Kruskal Algorithm
•  프림 알고리즘 Prim Algorithm 

위 그림을 보면 가중치가 부여된 그래프에서 나온 4개의 신장 트리가 있다. 각 신장 트리의 가중치의 합을 구해보면 가중치의 합에 대한 함수를 W(t)라고 정의했을 때 W(a) = 9, W(b) = 8, W(c) = 7, W(d) = 6이 된다. 4개의 트리중 가중치의 합이 가장 작은 신장 트리는 d이므로 위 그래프의 최소 비용 신장 트리는 d가 된다.

 

크루스칼 알고리즘 Kruskal Algorithm

크루스칼 알고리즘은 음의 가중치가 없는 무방향 그래프에서 최소 신장 트리를 찾는 알고리즘이다. 최소 신장 트리를 찾기 위해선 사이클 발생 여부를 판단할 수 있어야 한다. 사이클 발생 여부는 union find 알고리즘을 사용해서 판단한다. union find를 알면 크루스칼 알고리즘 이해에 도움되지만 모르더라도 아래 설명을 통해 어느정도 이해 가능할 것이다.

그래프에서 간선을 하나씩 추가하면 최소 신장 트리를 만드는 방식의 알고리즘이다. 간선을 추가할 때는 그리디 알고리즘을 사용하여 선택 당시 가중치가 최소인 간선을 선택한다.

 

크루스칼 알고리즘 시나리오 

1. 그래프 간선을 가중치 오름차순 정렬합니다.

 

2. 간선 a-b를 선택

3. 간선 a-d를 선택

4. 간선 b-d를 선택하면 a-b-d 사이클이 형성되므로 선택하지 않는다.

5. 간선 b-c를 선택, 선택된 간선의 갯수가, 정점의 갯수-1 만큼 되었으므로 종료합니다.

 

그렇다면 사이클은 어떻게 판단할까? 

사이클 판단하기 - Union & Find 활용

위에서 [4]번 과정에서 싸이클이면 넘어갔었는데, 이것을 코딩할 때는 Union&Find 자료구조를 사용한다.

• Union-Find 란?
  • Disjoint Set (서로소 집합) 을 표현하는 자료구조
  • 서로 다른 두 집합을 병합하는 Union 연산, 집합 원소가 어떤 집합에 속해있는지 찾는 Find 연산을 지원하기에 이러한 이름이 붙었음

 

 

간선 선택 전, 1번~4번 노드는 초기에 각각 서로소 집합 {1}, {2}, {3}, {4}로 표현될 수 있습니다.

• parent 배열은 각 정점의 root node(부모)를 표현한 배열
• 초기에는 자기 자신이 루트 노드가 되게 초기화 되어 있는 상태 (parent[i] = i)

 

가중치의 오름차순 정렬한 순서대로 간선 1-2 를 선택합니다.

이 때, 1번과 2번이 같은 집합으로 Union 연산에 의해 합쳐진 것입니다. 그리고 2번의 부모는 1번이 됩니다.

 

즉, 위에서 1-2 를 연결하면서 Union 연산에 의해 {1}, {2} 집합이 합쳐져서, 서로소 집합 {1, 2}, {3}, {4} 가 된 것입니다.

{1}, {2} 가 서로 합쳐질 수 있는 이유는 각 집합의 루트 노드가 다른 값 (1과 2)이었기 때문입니다.
({1}의 root node는 1, {2}의 root node는 2)

그리고 그 집합 내에서 제일 작은 숫자가 그 집합에서의 루트 노드(root node) 가 되게끔 가정합니다.

즉, 서로 루트 노드(부모)가 다른지 판단하고, 다르다면 Union 연산으로 합칩니다.

그 결과 2번 노드의 부모 노드는 1번이 되었으며, 1번과 2번은 같은 집합이 되었습니다.

 

1과 4를 연결해야 합니다. 1의 루트 노드는 1이고, 4의 루트 노드는 4 이므로 서로 다른 부모를 가집니다.

따라서 Union 연산으로 합칠 수 있으며, 합친 결과 {1, 2, 4} 집합이 되었습니다.

그리고 {1, 2, 4} 집합에서 루트 노드는 1 입니다. 즉, 2번의 부모는 1번이고, 4번의 부모도 1번입니다.

 

다음으로 간선 2-4를 선택합니다.

 

2와 4를 연결해야 합니다. 그런데, 2의 루트 노드는 1이고, 4의 루트 노드도 1 입니다.
(parent[2] = 1, parent[4] = 1 –> parent[2] == parent[4])

서로 부모가 같기 때문에 Union 연산을 하지 않습니다. 만약 합친다면 위 그래프처럼 사이클을 형성하게 되기 때문입니다.

즉 사이클을 형성하는지 알아보는 방법은, 각 노드의 부모 노드가 동일한지 아닌지 보는 것 !!!! 

집합 관점에서는, 이미 2와 4가 같은 집합에 속해 있으므로 거기서 또다시 Union 연산을 할 수 없는 것입니다.

 

 

자료참고

https://chanhuiseok.github.io/posts/algo-33/

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST)