Algorithm. 그래프 - 프림 알고리즘

1. 프림 알고리즘

• 한 정점에 연결된 간선들 중 하나씩 선택하며 최소 신장 트리를 만드는 알고리즘
  1. 임의의 정점을 하나 선택해서 시작
  2. 선택한 정점들과 인접한 정점들 중 최소 비용의 간선이 존재하는 정점을 선택
  3. 모든 정점이 선택될 때 까지 (2) 반복
• 두 종류의 상호 배타 집합(disjoint set)이 필요
  • 트리 정점 : 최소 신장 트리에 선택된 정점들
  • 비트리 정점 : 선택되지 않은 정점들

소스코드

# G : 그래프
# s : 시작 정점

def mst_prim(G, s):
    key = [INF] * N # 가중치를 무한대로 초기화
    pi = [None] * N # 트리에서 연결될 부모 정점 초기화
    visited = [False] * N # 방문 여부 초기화
    key[s] = 0 # 시작 정점의 가중치를 0으로 설정
    
    for _ in range(N): # 정점의 개수만큼 반복
    	minIndex = -1 
        min = INF
        for i in range(N): # 방문 안한 정점 중 최소 가중치 정점 찾기
            if not visited[i] and key[i] < min:
            	min = key[i]
                minIndex = i
        visited[minIndex] = True # 최소 가중치 정점 방문처리
        for v, val in G[minIndex]: # 선택 정점의 인접한 정점에 대해서
            if not visited[v] and val < key[v]: 
            	key[v] = val # 가중치 갱신
                pi[v] = minIndex # 트리에서 연결될 부모 정점 갱신

pi의 저장된 값이 최소 신장 트리를 의미한다.