[python] 크루스칼 알고리즘
크루스칼 알고리즘은 최소 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘 중 하나입니다. 최소 신장 트리란 주어진 그래프에서 모든 정점을 연결하면서 간선의 가중치의 합이 최소가 되는 부분 그래프입니다.
알고리즘 동작 원리
크루스칼 알고리즘은 간선들을 가중치의 오름차순으로 정렬한 뒤, 가중치가 가장 작은 간선부터 선택하여 사이클을 형성하지 않으면서 트리에 추가하는 것을 반복합니다.
- 그래프의 모든 간선을 가중치의 오름차순으로 정렬한다.
- 가중치가 가장 작은 간선을 선택한다.
- 선택한 간선을 그래프에 추가한다. 이때, 사이클을 형성하는지 확인한다.
- 모든 간선을 선택할 때까지 2-3을 반복한다.
예시 코드
def Kruskal(graph):
parent = dict()
rank = dict()
def make_set(v):
parent[v] = v
rank[v] = 0
def find(v):
if parent[v] != v:
parent[v] = find(parent[v])
return parent[v]
def union(v1, v2):
root1 = find(v1)
root2 = find(v2)
if root1 != root2:
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
minimum_spanning_tree = set()
for vertex in graph['vertices']:
make_set(vertex)
edges = list(graph['edges'])
edges.sort(key=lambda x: x[2])
for edge in edges:
vertex1, vertex2, weight = edge
if find(vertex1) != find(vertex2):
union(vertex1, vertex2)
minimum_spanning_tree.add(edge)
return minimum_spanning_tree
# 그래프 예시
graph = {
'vertices': ['A', 'B', 'C', 'D', 'E'],
'edges': [
('A', 'B', 1),
('A', 'C', 4),
('B', 'C', 2),
('B', 'D', 5),
('C', 'D', 1),
('C', 'E', 3),
('D', 'E', 6),
]
}
mst = Kruskal(graph)
print(mst)
위의 코드는 입력으로 주어진 그래프에서 크루스칼 알고리즘을 통해 최소 신장 트리를 구하는 예시 코드입니다.
시간 복잡도
크루스칼 알고리즘의 시간 복잡도는 간선의 개수(E)에 대해 최악의 경우 O(ElogE)입니다. 이는 대부분의 경우에 빠른 실행 시간을 보장합니다.