프림 알고리즘

최소 신장 트리 (MST)을 구할 경우

1. 크루스칼 알고리즘 (union find 활용)

2. 프림 알고리즘

 

프림 알고리즘

1. 우선순위 큐 ( heapq ) 활용

2. 우선순위 큐에 (가중치, 시작점) push

3. 간선-1 만큼 우선순위큐 pop

import heapq

# MST (최소 신장 트리 )
# 1. 크루스칼 알고리즘 ( UNION FIND 알고리즘)
# 2. 프림 알고리즘
# 프림 알고리즘
def prim(start):
    visited = [False]*(n+1) # 방문처리
    sum_w = 0

    # 우선순위큐 (가중치, 시작점)
    heap = []
    heapq.heappush(heap,(0,start))

    cnt = 0
    while heapq and cnt<n: # 간선-1 만큼 우선순위큐 pop
        w,v = heapq.heappop(heap)
        if not visited[v]:
            visited[v] = True
            sum_w += w
            cnt += 1
            for i in graph[v]:
                heapq.heappush(heap,i)