프림 알고리즘

개념

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법
• 최소 비용 트리를 구하기 위한 알고리즘

크루스칼 알고리즘 vs 프림 알고리즘

크루스칼 알고리즘은 가중치가 작은 간선부터 차례대로 포함하여 MST를 구성 → 간선의 개수가 적을 수록 유리함 (간선에 중점을 둠)

프림 알고리즘은 정점을 기준으로 가중치가 작은 곳으로 MST를 구성 → 정점의 개수가 적고 간선의 개수가 많을 때 유리함 (정점에 중점을 둠)

작동과정

1. 임의의 시작정점을 선택하여 비어있는 MST에 포함
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장함 → 가장 낮은 가중치를 선택
3. MST가 n-1개의 간선을 가질 때까지(모든 노드가 MST에 포함될 때까지) 반복함

시간복잡도

• 배열을 사용하는 경우 → 주 반복문의 정점의 수 V만큼 반복, 내부 반복문이 V만큼 반복 시간 복잡도는 $O(V^2)$
• PQ를 사용해서 개선 → 각 노드의 인접 간선을 찾는 시간은 $O(E)$, 각 간선을 힙에 넣는 시간은 $O(logV)$ 따라서 시간 복잡도는 $O(ElogV)$

예시코드

import heapq
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)
INF=sys.maxsize

v,e=map(int,input().split()) #노드 수, 간선 수
graph=[[] for _ in range(v+1)] #빈 그래프 생성
visited=[0]*(v+1)

#무방향 그래프 생성
for _ in range(e): 
    n1,n2,cost=map(int,input().split())
    graph[n1].append((n2,cost))
    graph[n2].append((n1,cost))

#프림 알고리즘
def prim(startNode):
    mst=[] #mst에 포함된 간선을 구해야 하는 경우
    mst_value=0 #최소 간선 비용
    #초기화
    heap=[]
    visited[startNode]=1 #시작 정점 방문
    for nextNode,cost in graph[startNode]: #시작정점에서 갈 수 있는 곳 힙에 넣기
        heapq.heappush(heap,(cost,startNode,nextNode))
    
    while heap:
        cost,n1,n2 = heapq.heappop(heap) #가중치가 가장 작은 간선 추출
        if not visited[n2]: #아직 방문하지 않았다면
            visited[n2]=1 #방문
            mst.append((n1,n2)) #mst 삽입
            mst_value+=cost #최소 간선비용 추가
            
            for n2Next,n2NextCost in graph[n2]: #다음 인접 간선 탐색
                if not visited[n2Next]: #아직 방문 안했다면
                    heapq.heappush(heap,(n2NextCost,n2,n2Next))
    return mst_value
prim(1)