[파이썬] 최소 신장 트리 (Minimum Spanning Tree) 알고리즘
최소 신장 트리 (Minimum Spanning Tree, MST)는 가중치가 있는 무방향 그래프에서 모든 정점을 포함하는 트리 중에서 가중치의 합이 최소인 트리를 찾는 알고리즘입니다. 이러한 트리는 신장 트리(Spanning Tree)라고도 불립니다. MST 알고리즘은 여러 가지 방법으로 구현할 수 있지만, 이번 글에서는 Kruskal’s 알고리즘을 사용하여 MST를 찾는 방법을 살펴보겠습니다.
Kruskal’s 알고리즘
Kruskal’s 알고리즘은 그리디 알고리즘을 기반으로 하며, 다음과 같은 단계로 동작합니다:
- 그래프의 간선들을 가중치 순으로 정렬합니다.
- 가장 작은 가중치를 가진 간선부터 탐색합니다.
- 해당 간선을 MST에 추가합니다. 단, 해당 간선이 사이클을 형성하지 않는 경우에만 추가할 수 있습니다.
- 모든 간선을 탐색할 때까지 단계 2와 단계 3을 반복합니다.
MST를 효율적으로 구현하기 위해서는 “Union-Find” 알고리즘을 사용하여 사이클을 확인할 수 있어야 합니다. Union-Find는 간단한 자료구조로서 집합의 특정 원소가 속한 집합을 빠르게 확인할 수 있습니다.
예시 코드
아래는 Kruskal’s 알고리즘을 사용하여 MST를 찾는 예시 코드입니다. 이 코드는 Python 3으로 작성되었습니다.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
def kruskal_mst(graph):
mst = []
edges = []
n = len(graph)
for u in range(n):
for v in range(u + 1, n):
if graph[u][v] != 0:
edges.append((graph[u][v], u, v))
# 간선을 가중치 순으로 정렬
edges.sort()
uf = UnionFind(n)
for edge in edges:
weight, u, v = edge
if uf.find(u) != uf.find(v):
uf.union(u, v)
mst.append(edge)
return mst
# 예시 그래프
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
mst = kruskal_mst(graph)
for edge in mst:
print(edge)
위 코드는 입력 그래프의 인접 행렬을 통해 MST를 찾습니다. graph는 예시로 주어진 그래프를 나타냅니다. Kruskal’s 알고리즘을 사용하여 MST를 찾은 후, 간선들을 출력하는 예시 코드입니다.
이렇게 Kruskal’s 알고리즘을 활용해서 MST를 찾을 수 있습니다. 다른 알고리즘들인 Prim’s 알고리즘 등도 더 공부해 볼 수 있습니다. MST는 그래프 알고리즘에서 중요한 개념이므로, 추가적인 학습을 통해 더 깊이있게 이해해보세요.
참고: 위키피디아 - Minimum Spanning Tree