크루스칼 알고리즘(Kruskal Algorithm)
크루스칼 알고리즘은 '최소 신장 트리'를 찾아내기 위한 알고리즘이다. 따라서 '신장 트리'와 '최소 신장 트리'가 무엇인지부터 이해해야 한다.
신장 트리(Spanning Tree)
신장 트리는 어떤 그래프가 존재할 때, 해당 그래프를 구성하는 모든 노드를 포함하면서 사이클은 존재하지 않는 부분 그래프를 말한다. 따라서 하나의 그래프에서 여러 개의 신장 트리가 나올 수 있다.
예를 들어 다음과 같은 그래프가 있다고 하자.
이 그래프에서 나올 수 있는 신장 트리는 다음과 같이 여러 가지가 있을 수 있다.
최소 신장 트리(Minimum Spanning Tree)
그래프 중 위의 그래프와 같이 간선의 '비용'(혹은 가중치)이 존재하는 그래프도 있다. 이때 '신장 트리' 중 그 비용의 합이 최소가 되는 신장 트리를 최소 신장 트리라 한다. 상기 그래프의 경우 다음 신장 트리가 최소 신장 트리가 된다.
기본 동작 과정
크루스칼 알고리즘의 동작 과정을 간단히 정리하면 다음과 같다.
1. 주어진 모든 간선 정보를 비용이 낮은 순서(오름차순)로 정렬한다.
2. 각 간선 정보를 하나씩 확인하면서 현재 간선이 노드들 간의 사이클을 발생시키는지를 확인한다.
3. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함시키고, 사이클이 발생할 경우 포함시키지 않는다.
이를 보면 각 간선의 정보를 혹인해 '노드 간의 사이클 발생 여부'를 확인해야 한다. 따라서 Union-Find 알고리즘을 이용해 사이클 발생 여부를 확인하며, Union-Find 연산이 크루스칼 알고리즘의 핵심이 된다.
Example
상기의 그래프를 예로 들어 단계별로 과정을 정리해 보자. 상기 그래프의 간선 정보를 비용을 기준으로 오름차순 정렬하면 다음과 같이 정리할 수 있다.
| 간선 | (1, 2) | (2, 4) | (1, 5) | (3, 5) | (4, 5) | (2, 3) |
|---|---|---|---|---|---|---|
| 비용 | 1 | 2 | 3 | 4 | 5 | 6 |
-
첫 간선 정보인 (1, 2)의 부모 노드를 각각 확인한다. 현재는 부모 노드의 값이 각각 자기 자신이므로 사이클이 발생하지 않으며, 따라서 신장 트리에 포함한다. 또한 부모 노드의 값 중 1이 더 작기 때문에 2번 노드의 부모 노드 값을 1로 바꿔 준다.
<현재 간선 정보>간선 (1, 2) (2, 4) (1, 5) (3, 5) (4, 5) (2, 3) 비용 1 2 3 4 5 6 <부모 노드 테이블>
노드 번호 1 2 3 4 5 부모 노드 값 1 2→1 3 4 5 -
두 번째 간선 정보인 (2, 4)의 비용은 2이다. 2의 부모 노드의 값은 1, 4의 부모 노드 값은 4이므로 사이클이 발생하지 않는다. 따라서 최소 신장 트리에 포함시킨다.
이때 4의 부모 노드 값은 2인데(4보다 2가 작으므로), 2의 부모 노드 값은 1로 수정되었으므로 4의 부모 노드 값 역시 1로 수정한다.
<현재 간선 정보>간선 (1, 2) (2, 4) (1, 5) (3, 5) (4, 5) (2, 3) 비용 1 2 3 4 5 6 <부모 노드 테이블>
노드 번호 1 2 3 4 5 부모 노드 값 1 1 3 4→2→1 5 -
3번째 간선 정보 (1, 5)의 비용은 3이고 1과 5의 부모 노드 값은 다르므로 최소 신장 트리에 포함시킨다. 또한 5번 노드의 부모 노드 값을 1로 수정한다.
<현재 간선 정보>간선 (1, 2) (2, 4) (1, 5) (3, 5) (4, 5) (2, 3) 비용 1 2 3 4 5 6 <부모 노드 테이블>
노드 번호 1 2 3 4 5 부모 노드 값 1 1 3 1 5→1 -
4번째 간선 정보 (3, 5)의 비용은 4이며, 부모 노드 값 역시 다르므로 위와 동일한 작업을 수행한다.
<현재 간선 정보>간선 (1, 2) (2, 4) (1, 5) (3, 5) (4, 5) (2, 3) 비용 1 2 3 4 5 6 <부모 노드 테이블>
노드 번호 1 2 3 4 5 부모 노드 값 1 1 3→1 1 1 -
다섯 번째 간선 정보 (4, 5)를 보자. 이 경우 4와 5의 부모 노드 값이 모두 1로 동일하며, 따라서 사이클을 발생시킨다. 그러므로 최소 신장 트리에 포함시키지 않고 넘어간다.
<현재 간선 정보>
간선 (1, 2) (2, 4) (1, 5) (3, 5) (4, 5) (2, 3) 비용 1 2 3 4 5 6 <부모 노드 테이블>
노드 번호 1 2 3 4 5 부모 노드 값 1 1 1 1 1 -
여섯 번째 간선 정보 (2, 3)의 경우에도 두 노드의 값이 모두 1로 동일하므로 최소 신장 트리에 포함시키지 않는다.
모든 연산이 종료된 후 최소 신장 트리에 포함된 간선 정보만을 나열하면 [(1, 2), (2, 4), (1, 5), (3, 5)]이며, 이는 다음의 최소 신장 트리에 표시된 간선과 동일함을 알 수 있다.
코드 구현
크루스칼 알고리즘은 Union-Find 연산과 사이클 판별 로직을 활용해 구현할 수 있다(관련 포스트 참고).
){kind=link}
# [연결 노드 A, 연결 노드 B, 비용(가중치)]
edges = [[2, 4, 2], [4, 5, 5], [1, 2, 1], [3, 5, 4], [1, 5, 3], [2, 3, 6]]
n = len(edges)
# 간선 정보를 비용을 기준으로 정렬
edges.sort(key=lambda x: x[2])
# 부모 노드 테이블 생성 후 초기화
parent = [0] * (n+1)
for i in range(1, n+1):
parent[i] = i
# find 함수와 union 함수 선언
def find(parent, x):
# 자기 자신이 루트 노드가 아닐 경우 루트 노드를 찾을 때까지 재귀적으로 호출
if parent[x] != x:
# return find(parent, parent[x])
parent[x] = find(parent, parent[x]) # 불필요한 재귀를 줄이기 위해 테이블 즉시 갱신
return parent[x]
def union(parent, a, b):
a = find(parent, a)
b = find(parent, b)
# 각각의 부모 노드 값을 비교하여 작은 값으로 갱신
if a < b:
parent[b] = a
else:
parent[a] = b
# 간선 정보를 순회하면서 크루스칼 알고리즘 수행
def kruskal(edges, parent):
tree_cost = 0
for i in range(n):
a, b, cost = edges[i]
# 두 노드 간의 사이클 여부 확인
if find(parent, a) != find(parent, b):
union(parent, a, b)
tree_cost += cost
return tree_cost
print(kruskal(edges, parent))참고 자료
