프림 알고리즘: 하나의 트리를 가장 싼 연결로 확장하기
프림 알고리즘은 무방향 가중 그래프에서 한 정점을 출발점으로 삼아 최소 신장 트리를 성장시킨다. 현재 트리 안의 정점과 바깥 정점을 잇는 간선 중 가장 가벼운 것을 선택한다. 전체 간선을 비용순으로 고르는 방식과 달리 매 순간 하나의 연결된 트리를 유지한다.
이미 선택한 정점 집합에서 바깥으로 이어지는 최소 간선을 선택한다.
트리의 경계가 선택 범위다
A—B 비용 4, A—C 비용 1, C—B 비용 2가 있다면 A에서 처음 후보는 A—B와 A—C다. C를 비용 1로 붙인 뒤 C—B 비용 2가 새 후보가 되어 B를 더 싸게 연결한다. B를 붙이는 비용은 A에서 B까지의 누적 경로 비용이 아니라 경계를 가로지르는 한 간선의 비용이다.
이 차이는 최단 경로 알고리즘과 구별되는 부분이다. 프림은 각 정점에 대한 경로 길이 합이 아니라 선택한 간선 전체의 가중치 합을 최소화한다. 시작 정점이 달라도 최소 총합은 같지만 동률이 있으면 트리 모양은 달라질 수 있다.
import heapq
def prim(graph, source):
visited = set()
candidates = [(0, source, None)]
tree_edges = []
total_cost = 0
while candidates:
edge_cost, vertex, predecessor = heapq.heappop(candidates)
if vertex in visited:
continue
visited.add(vertex)
total_cost += edge_cost
if predecessor is not None:
tree_edges.append((predecessor, vertex, edge_cost))
for neighbor, cost in graph[vertex]:
if neighbor not in visited:
heapq.heappush(candidates, (cost, neighbor, vertex))
return tree_edges, total_cost, visited
코드는 이웃을 (정점, 비용)으로 저장하고, 동률 때 정점 등을 비교할 수 있다고 가정한다. 비교 불가능한 객체라면 큐 항목에 별도 순번을 넣는다. 여러 번 들어온 후보 중 이미 포함된 정점으로 가는 것은 버린다.
선택이 안전한 이유
현재 트리의 정점 집합과 나머지 정점을 나누면 하나의 컷이 된다. 그 컷을 가로지르는 최소 간선을 선택하므로 최소 신장 트리의 컷 성질을 적용할 수 있다. 큐에 있는 간선 전체 중 최소라도 양끝이 이미 안쪽이면 경계 간선이 아니므로 제외해야 한다.
중복 간선 후보를 저장하는 힙 구현은 O(E log E)로 설명할 수 있다. 정점별 최선 연결 비용을 관리하는 인덱스 힙은 O((V+E)log V)이고, 행렬과 선형 선택을 쓰면 O(V²)다. 그래프의 밀도와 구현 방식에 맞는 표현이 필요하다.
출발점이 있는 연결 요소만 처리되므로 visited의 크기를 전체 정점 수와 비교해야 한다. 전체 최소 신장 숲을 원하면 미방문 요소마다 다시 실행한다. 음수 가중치도 허용된다.
프림의 매 단계는 연결된 트리를 유지하지만 전체 입력이 연결되었다는 보장을 만들지는 않는다. 결과 간선 수, 도달한 정점 수, 비용 총합을 구별해 반환하면 불완전한 결과를 완성된 신장 트리로 오해하는 일을 막을 수 있다.