최소 신장 트리 편집하기 (부분)

===[[프림 알고리즘]] (Prim's Algorithm)===
프림 알고리즘은 시작 정점에서 출발하여,  MST에 포함되지 않은 정점 중 최소 가중치의 간선을 추가하는 방식이다.

'''알고리즘 과정:'''
#임의의 정점에서 시작하여 MST에 추가한다.
#MST에 연결된 간선 중 최소 가중치를 가지는 간선을 선택한다.
#선택된 간선을 MST에 추가한 후, 해당 간선의 도착 정점을 MST에 포함시킨다.
#모든 정점이 포함될 때까지 반복한다.
'''슈도코드:'''<pre>
PrimMST(graph, start):
    MST = []
    minHeap = PriorityQueue()
    visited = set()

    minHeap.push((0, start))  # 시작 정점

    while minHeap is not empty:
        weight, u = minHeap.pop()
        if u in visited:
            continue
        visited.add(u)
        MST.append(u)

        for v, w in graph[u]:
            if v not in visited:
                minHeap.push((w, v))

    return MST
</pre>'''파이썬 코드:'''<syntaxhighlight lang="python">
import heapq

def prim_mst(graph, start=0):
    mst = []
    visited = set()
    min_heap = [(0, start)]  # (가중치, 정점)
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append(u)

        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (w, v))

    return mst
</syntaxhighlight>