[파이썬] 크루스칼 알고리즘의 개념과 구현
크루스칼 알고리즘은 그래프에서 최소 비용으로 모든 노드를 연결하는 최소 신장 트리를 구하는 알고리즘입니다. 이 알고리즘은 간선을 기준으로 선택하며, 사이클을 형성하지 않으면서 간선을 추가하는 방식으로 동작합니다. 이번 블로그에서는 크루스칼 알고리즘의 개념과 구현 방법에 대해 알아보겠습니다.
개념
크루스칼 알고리즘의 개념은 다음과 같습니다:
- 간선들을 비용의 오름차순으로 정렬합니다.
- 가장 작은 비용의 간선부터 선택하며, 해당 간선을 추가합니다.
- 추가된 간선이 사이클을 형성하지 않으면서, 모든 노드를 연결할 때까지 2번의 과정을 반복합니다.
크루스칼 알고리즘은 Union-Find 자료구조를 사용하여 사이클을 확인합니다. 두 노드가 같은 집합에 속해 있으면 사이클이 형성된 것으로 간주합니다.
구현
이제 크루스칼 알고리즘을 Python으로 구현해보겠습니다. 아래는 크루스칼 알고리즘을 구현한 코드 예시입니다.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def union(self, a, b):
self.parent[self.find(a)] = self.find(b)
def find(self, a):
if self.parent[a] != a:
self.parent[a] = self.find(self.parent[a])
return self.parent[a]
def kruskal(graph):
edges = []
for from_node in range(len(graph)):
for to_node, cost in graph[from_node]:
edges.append((cost, from_node, to_node))
edges.sort() # 간선을 비용의 오름차순으로 정렬
mst = []
uf = UnionFind(len(graph))
for cost, from_node, to_node in edges:
if uf.find(from_node) != uf.find(to_node): # 사이클을 형성하지 않는지 확인
mst.append((from_node, to_node, cost))
uf.union(from_node, to_node)
return mst
# 예시 그래프
graph = {
0: [(1, 4), (7, 8)],
1: [(0, 4), (2, 8), (7, 11)],
2: [(1, 8), (3, 7), (5, 4), (8, 2)],
3: [(2, 7), (4, 9), (5, 14)],
4: [(3, 9), (5, 10)],
5: [(2, 4), (3, 14), (4, 10), (6, 2)],
6: [(5, 2), (7, 1), (8, 6)],
7: [(0, 8), (1, 11), (6, 1), (8, 7)],
8: [(2, 2), (6, 6), (7, 7)]
}
mst = kruskal(graph)
print(mst) # 출력: [(6, 7, 1), (2, 8, 2), (5, 6, 2), (0, 1, 4), (2, 5, 4), (2, 3, 7), (3, 4, 9)]
이 코드에서 graph는 예시 그래프로, 인접 리스트 형태로 표현되어 있습니다. kruskal 함수는 주어진 그래프를 기반으로 크루스칼 알고리즘을 수행하고, 최소 신장 트리(mst)를 반환합니다. 출력 결과는 간선의 정보와 비용으로 이루어진 튜플들의 리스트로 나타납니다.
이처럼 크루스칼 알고리즘을 구현하여 최소 비용의 신장 트리를 구할 수 있습니다. 주어진 그래프에 따라 비용과 간선의 정보를 적절히 수정하여 다양한 상황에 적용할 수 있습니다.