[파이썬] 최소 스패닝 트리 (Minimum Spanning Trees) 알고리즘
최소 스패닝 트리 (Minimum Spanning Trees) 알고리즘은 그래프의 모든 정점을 포함하는 트리 중에서 간선의 가중치 합이 최소인 트리를 찾는 알고리즘입니다. 이 트리는 네트워크, 도로망, 회로 등의 문제에서 최적의 해결 방법으로 사용됩니다.
프림 알고리즘 (Prim’s Algorithm)
프림 알고리즘은 한 정점에서부터 시작하여 트리를 확장해가는 방법으로 최소 스패닝 트리를 찾는 알고리즘입니다. 아래는 프림 알고리즘의 파이썬 구현 예제입니다.
from queue import PriorityQueue
def prim(graph):
start_node = list(graph.keys())[0] # 임의의 시작 노드 선택
visited = set([start_node])
edges = PriorityQueue()
for edge in graph[start_node]:
edges.put(edge)
mst = []
total_cost = 0
while not edges.empty():
cost, node1, node2 = edges.get()
if node2 not in visited:
visited.add(node2)
mst.append((node1, node2, cost))
total_cost += cost
for edge in graph[node2]:
if edge[1] not in visited:
edges.put(edge)
return mst, total_cost
위의 코드에서 graph는 인접 리스트 형태로 주어진 그래프입니다. PriorityQueue를 사용하여 간선의 가중치에 따라 오름차순으로 정렬된 큐를 유지하면서 트리를 확장합니다. 최종적으로 mst는 최소 스패닝 트리의 간선들이 저장된 리스트이고 total_cost는 간선들의 가중치 합입니다.
이제 프림 알고리즘을 사용하여 최소 스패닝 트리를 찾아보겠습니다.
graph = {
'A': [('B', 7), ('D', 5)],
'B': [('A', 7), ('D', 9), ('C', 8), ('E', 7)],
'C': [('B', 8), ('E', 5)],
'D': [('A', 5), ('B', 9), ('E', 15), ('F', 6)],
'E': [('C', 5), ('B', 7), ('D', 15), ('F', 8), ('G', 9)],
'F': [('D', 6), ('E', 8), ('G', 11)],
'G': [('E', 9), ('F', 11)]
}
mst, total_cost = prim(graph)
print("Minimum Spanning Tree:")
for edge in mst:
print(f"{edge[0]} -- {edge[1]} : {edge[2]}")
print(f"Total cost: {total_cost}")
위의 코드는 주어진 그래프에서 최소 스패닝 트리를 찾아서 출력하는 예제입니다. 예제 그래프에 대한 결과는 다음과 같습니다.
Minimum Spanning Tree:
A -- D : 5
D -- F : 6
D -- B : 9
B -- E : 7
E -- C : 5
E -- G : 9
Total cost: 41
프림 알고리즘을 통해 최소 스패닝 트리를 찾는 방법에 대해 알아보았습니다. 다음 포스트에서는 크루스칼 알고리즘에 대해 다루도록 하겠습니다.