최소신장트리를 구하기 위한 쿠르스칼 알고리즘 (Kruskal's algorithm for Minimum Spanning Tree)

[신장트리의 의미]

신장트리에서 신장(身長)은 사전적으로 머리 끝에서 발 끝까지라는 의미이다. 어느 정점에서 시작하더라도 트리의 모든 leaf까지 도달할 수 있기 때문에 신장트리라고 명명한 것이 아닌가 생각된다. 영어로는 spanning tree인데 spanning의 의미는 '걸쳐서 이어진'이다.  즉, 트리 구조 특성상 순환이 발생하지 않으며 모든 노드가 이어진 부분 그래프를 신장트리라고 한다.

 

[최소신장트리 (Minimum Spanning Tree)]

신장트리 가운데 모든 간선 비용의 합이 최소인 것을 최소신장트리라고 한다. 최소신장트리는 네트워크, 도로건설, 배관, 전기회로 등의 최적화에 활용할 수 있다.

 

 

[서로소 집합과 무방향 그래프의 순환 발생 여부 확인]

그래프에서 최소신장트리를 구하려면 순환을 유발하는 간선을 배제해야할 필요가 있는데, 무방향 그래프 내에서의 순환 유발 간선은 서로소 집합을 사용하면 확인할 수 있다.

서로소 집합이라 함은 동일 원소를 갖지 않는 부분 집합들을 원소로 갖는 집합으로 다시 말해 모든 원소들 간의 교집합이 공집합인 부분집합들을 원소로 갖는 집합을 말한다.

전체 집합 원소를 서로소 집합 구조로 나누기 위한 알고리즘은 다음과 같다.

1. 노드(여기서는 원소)간 연결을 위한 union 연산을 진행한다.
   1. union 연산에 사용되는 두 원소 A, B의 부모인 A'와 B'를 find연산을 통해 찾는다.
   2. A' < B'이면 B'의 값을  A'로 업데이트한다. 반대로 A' > B'이면 A'의 값을 B'로 업데이트한다.
2. 모든 union 연산을 반복한다.

위의 의사코드를 구현하면 다음과 같다.

def find_parent(parent, x):
    if parent[x] != x:
        return find_parent(parent, parent[x])
    return x


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


v, e = map(int, input().split())
parent = dict()
for i in range(v + 1):
    parent[i] = i

for i in range(e):
    a, b = map(int, input().split())
    union_parent(parent, a, b)
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
    print(find_parent(parent, i), end=' ')
print()
print('부모 테이블: ', end='')
for i in range(1, v + 1):
    print(parent[i], end=' ')

만약 집합 S = {1, 2, 3, 4, 5} 이고 union연산이 (4, 5), (3, 4), (2, 3), (1, 2)의 순서로 실행되는 경우 원소와 각 부모원소 간의 관계 테이블은 아래와 표와 같아진다. 5의 부모원소를 찾기 위해 find 연산을 하는 경우 4 -> 3 -> 2 -> 1 순서로 선형탐색을 하게 되어 비효율 적으로 동작한다.

원소	1	2	3	4	5
부모원소	1	1	2	3	4

이를 해결하기 위해 경로 압축 기법을 사용한다. 경로 압축 기법은 부모노드를 찾아가면서 선형탐색했던 구간의 모든 노드들의 값을 최종적으로 찾은 부모노드로 모두 업데이트 해주는 것이다. 이를 위해 위의 코드에서 find_parent()를 다음과 같이 변경한다.

def find_parent(parent, x):
    if parent[x] != x:
    	# 부모노드를 재귀호출 끝에 찾은 값으로 모두 업데이트 해준다.
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

위와 같이 find_parent()를 수정하면 5의 부모노드를 찾을 때 O(V)만큼 시간이 소요되지만, 이후 동일 집합 내에 다른 요소들을 찾을 때는 O(1)로 부모 노드의 값을 찾을 수 있게 된다.

 

 

위에서 살펴본 서로소 집합을 사용하여 그래프의 순환 발생 여부를 확인하는 방법은 다음과 같다.

1. 두 노드의 부모노드를 확인하여
   1. 부모노드가 서로 다르면 두 노드에 대해 union 연산
   2. 부모노드가 서로 같으면 순환이 발생한 것임 (부모노드가 같다는 것은 어떤 경로로 가던 부모노드로 도착하게 된다는 의미이다. 즉, 현재 순환을 발생시키는지 확인하고 있는 간선을 구성하는 두 노드 가운데 어디서 출발하던지 현재 간선 또는 다른 간선을 통해 부모노드에 도착할 수 있으므로 순환이 발생했다고 볼 수 있다.)
2. 그래프 내의 모든 간선에 대해 1번을 반복

무방향 그래프에서 순환 발생 여부를 확인하는 코드는 다음과 같다.

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


v, e = map(int, input().split())
parent = [0]
for i in range(1, v + 1):
    parent.append(i)
cycle = False
for i in range(e):
    a, b = map(int, input().split())
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

if cycle:
    print("There are some cycles in the graph")
else:
    print("There is no cycle in the graph")

 

 

[kruskal 알고리즘]

최소신장트리를 구하는 알고리즘 가운데 대표적인 것이 크루스칼(kruskal's) 알고리즘이며 구 구현은 다음과 같다.

 

1. 간선 데이터를 가중치를 기준으로 오름차순으로 정렬한다.
2. 가중치가 낮은 간선부터 순차적으로 순환이 발생하는지 확인하여 순환이 발생하지 않은 경우에만 최소신장트리에 그 간선을 포함시킨다.
3. 2번을 모든 간선에 대해 수행한다.

 

[kruskal 알고리즘의 구현]

import heapq
import sys

fast_input = sys.stdin.readline


def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]


def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b


v, e = map(int, input().split())
parent = [0]
for i in range(1, v + 1):
    parent.append(i)
edges = []
result = 0
for _ in range(e):
    a, b, cost = map(int, fast_input().rstrip().split())
    heapq.heappush(edges, (cost, a, b))
while edges:
    cost, a, b = heapq.heappop(edges)
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
print(result)

 

[kruskal 알고리즘의 시간복잡도]

kruskal 알고리즘에서 가장 시간이 많이 소요되는 작업은 간선을 정렬하는 것이다. 따라서 간선을 E라고 했을 때 시간복잡도는 O(E log E)가 된다.