최소 신장 트리 (Minimum Spanning Tree)이란?
신장 트리 (Spanning Tree)로 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프입니다. 즉, 신장 트리의 조건은 다음과 같습니다.
-
본래의 그래프의 모든 노드를 포함
-
모든 노드가 서로 연결
-
트리의 속성을 만족
이러한 `신장 트리` 중에서 `최소 신장 트리(MST)`는 간선의 가중치 합이 최소인 `Spanning Tree` 이므로 코딩 테스트에서 자주 나오지는 않지만 나오는 경우가 종종 있기 때문에 알아야 하는 알고리즘입니다.
MST의 대표적인 알고리즘은 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데 먼저, 크루스칼 알고리즘을 알아보겠습니다.
크루스칼 알고리즘(Kruskal's Algorithm)
크루스칼 알고리즘의 논리적인 순서는 다음과 같습니다.
-
모든 정점을 독립적인 집합으로 만든다.
-
모든 간선의 비용을 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
-
두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것)
눈 앞의 최소 비용을 선택해서 결과적으로 최적의 솔루션을 찾는 것이 탐욕(Greedy) 알고리즘을 기반으로 하고 있는 것 같습니다.
Union-Find 알고리즘
대충 크루스칼 알고리즘이 조금이라도 어떻게 이루어지는지 파악을 하셨다면 이제 어떻게 노드를 찾고, 연결하는지 의문이 드실 겁니다.(사실, 저도 제대로 이해 못함 😂)
크루스칼 알고리즘을 위해서는 Union-Find 알고리즘을 사용을 해야하는데 어디서 많이 들어본 알고리즘이죠? Disjoin Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘입니다. 간단하게 노드 중 연결된 노드를 찾거나 노드들을 서로 연결할 때 사용한다고 생각하시면 됩니다.
Union-Find 알고리즘에서 Union은 어떤 걸 담당하는지 Find는 어느 기능을 하는 지 보겠습니다.
1. 초기화
-
n 개의 원소가 개별 집합으로 이뤄지도록 초기화
2. Union
- 두 개별 집합을 하나의 집합으로 합침, 두 트리를 하나의 트리로 만듬
#### 3. Find
- 여러 노드가 존재할 때, 두 개의 노드를 선택해서 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해 각 그룹의 최상단 원소(root)를 확인
이러한 Union-Find 알고리즘을 사용할 때 Union 순서에 따라서 최악의 경우 Linked List와 같은 형태가 될 수 있기 때문에 union-by-rank, path compression 기법을 사용하는데 참 복잡한 알고리즘인 것 같습니다.
4. Union-by-Rank
Union-by-rank는 각 트리에 대해 높이(rank)를 기억해두고 Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙입니다. 즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 합니다.
높이가 *h-1* 인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 *1* 증가 시켜주고, 다른 쪽의 트리를 해당 트리에 붙여줍니다.
초기화시, 모든 원소는 높이(rank)가 *0* 인 개별 집합인 상태에서 하나씩 원소를 합칠 때 `union-by-rank` 기법을 사용한다면 시간 복잡도는 **O(N)** 이 아닌 **O(logN)** 로 낮출 수 있습니다.
5. Path Compression
Path compression은 Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법으로 Find를 실행한 노드는 이후부터 루트 노드를 한 번에 알 수 있습니다.
크루스칼 알고리즘(Kruskal's Algorithm) 구현
mygraph = {
'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
'edges': [
(7, 'A', 'B'),
(5, 'A', 'D'),
(7, 'B', 'A'),
(8, 'B', 'C'),
(9, 'B', 'D'),
(7, 'B', 'E'),
(8, 'C', 'B'),
(5, 'C', 'E'),
(5, 'D', 'A'),
(9, 'D', 'B'),
(7, 'D', 'E'),
(6, 'D', 'F'),
(7, 'E', 'B'),
(5, 'E', 'C'),
(7, 'E', 'D'),
(8, 'E', 'F'),
(9, 'E', 'G'),
(6, 'F', 'D'),
(8, 'F', 'E'),
(11, 'F', 'G'),
(9, 'G', 'E'),
(11, 'G', 'F')
]
}
parent = dict()
rank = dict()
def find(node):
# path compression 기법
# 자기 노드의 부모노드가 자기가 아님 -> 그 위에 루트노드가 있음
if parent[node] != node:
# 부모 노드를 찾아감
parent[node] = find(parent[node])
# 최종적으로 루트 노드를 반환
return parent[node]
def union(node_v, node_u):
root1 = find(node_v)
root2 = find(node_u)
# union-by-rank 기법
# root2가 root1로 연결되어야 함
if rank[root1] > rank[root2]:
# 즉, root1이 root2의 부모노드로 됨
parent[root2] = root1
else:
parent[root1] = root2
# 루트의 랭크가 동일한 경우 아무곳에 연결해도 상관없음
if rank[root1] == rank[root2]:
rank[root2] += 1
def make_set(node):
parent[node] = node
rank[node] = 0
def kruskal(graph):
mst = list()
# 1. 초기화 - 각 노드별로 부분집합을 만듬
for node in graph['vertices']:
make_set(node)
# 2. 간선 weight 기반 sorting
edges = graph['edges']
edges.sort()
# 3. 간선 연결 (사이클 없는)
for edge in edges:
weight, node_v, node_u = edge
# 루트 노드가 다른 것을 찾음(사이클이 없음)
if find(node_v) != find(node_u):
union(node_v, node_u)
mst.append(edge)
return mst