프림 알고리즘

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

 

대표적인 최소 신장 트리 알고리즘으로 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고 해장 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해나가는 방식이다.

 

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

 

두 개의 알고리즘 다 탐욕 알고리즘을 기초로 하고 있다. 

다만 크루스칼 알고리즘은 가장 가중치가 작은 간선을 선택하면서 MST를 구하지만

프림 알고리즘은 특정 정점에서 시작해 해정 정점에 연결된 가장 적은 가중치를 가진 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구한다.

파이썬 코드

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))
        --여기서 노드들의 연결된 간선들을 adjacent_edges에 저장한다.
        
        connected_nodes = set(start_node) 
        -- 연결된 집합을 나타낸다.
        candidate_edge_list = adjacent_edges[start_node]
        heapify(candidate_edge_list)
        --해당 노드의 인접 간선들을 힙구조에 저장한다.
        
        while candidate_edge_list:
         weight,n1,n2 = heappop(cadidate_edge_list)
         --가장 적은 가중치의 간선을 최소 힙에서 꺼낸뒤
         
         if n2 not in connected_nodes:
         --만약 간선으로 연결된 노드가 연결집합에 존재하지않으면
          connected_nodes.add(n2)
          집합에 추가하고 mst의 일부트리로 저장한다
          mst.append((weight,n1,n2))
          
          --이후 추가된 노드에 연결된 간선을 또다시 후보에 등록하고 반복한다.
          --만약 현재 간선에 연결된 노드가 집합에 들어있다면 반복하지 않는다.
          for edge in adjacent_edges[n2]:
          if edge[2] not in connected_nodes:
          	heappush(candidate_node_list,edge)
            
         return mst
          
        

 

시간복잡도는 간선을 힙 구조로 저장하는데 O(E)와 간선을 최소 힙 구조로 탐색해 계산하는 logE를 합쳐

O(ElogE)라고 할 수 있다.

 

다만 개선된 프림 알고리즘에서는 간선의 수가아닌 노드의 수로 계산하여 더 향상된 알고리즘을 제공한다.