[알고리즘] 프림 알고리즘 (최소신장트리 2)

프림 알고리즘 (Prim's algorithm)

대표적인 신장 트리 알고리즘

• 크루스칼 알고리즘, 프림 알고리즘

프림 알고리즘

• 시작 노드를 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 노드를 선택하고, 해당 노드에서 다시 최소 간선으로 연결된 노드를 선택하는 방식으로 최소 신장 트리를 확장해가는 방식

크루스칼 알고리즘과 프림 알고리즘 비교

• 둘 다, 탐욕 알고리즘을 기초로 하고 있음
• 크루스칼 알고리즘은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
• 프림 알고리즘은 특정 노드에서 시작, 해당 노드에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 노드들에 연결된 간선 중에서 가장 가중치가 작은 간선을 선택하는 방식으로 MST를 구함

그림

1. 임의의 노드를 선택, '연결된 노드 집합'에 삽입
2. 선택된 노드에 연결된 간선들을 '간선 리스트'에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 노드가 '연결된 노드 집합'에 이미 들어 있다면, 스킵함 (cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 노드가 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복
   
   
   

코드

myedges = [
    (7, 'A', 'B'), (5, 'A', 'D'),
    (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'),
    (5, 'C', 'E'),
    (7, 'D', 'E'), (6, 'D', 'F'),
    (8, 'E', 'F'), (9, 'E', 'G'),
    (11, 'F', 'G')
]

from collections import defaultdict
from heapq import *

def prim(start_node, edges):
    mst = list()
    adjacent_edges = defaultdict(list)
    for weight, n1, n2 in edges:
        adjacent_edges[n1].append((weight, n1, n2))
        adjacent_edges[n2].append((weight, n2, n1))

    connected_nodes = set(start_node)
    candidate_edge_list = adjacent_edges[start_node]
    heapify(candidate_edge_list)
    
    while candidate_edge_list:
        weight, n1, n2 = heappop(candidate_edge_list)
        if n2 not in connected_nodes:
            connected_nodes.add(n2)
            mst.append((weight, n1, n2))
            
            for edge in adjacent_edges[n2]:
                if edge[2] not in connected_nodes:
                    heappush(candidate_edge_list, edge)

    return mst

시간 복잡도

O(E logE)

개선된 프림 알고리즘