프림 알고리즘

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

특정 연결 노드를 선택 했을때 탐욕 알고리즘에 따라 진행하는 방법으로 현재 선택된 그래프 중에서 가장 작은 값을 선택하며 노드를 연결해 나가는 방식

1. 임의의 정점 선택
2. 연결된 노드 집합에 선택된 노드를 넣고 그 노드의 간선 중 가장 값이 적은 걸 선택함.
3. 선택해서 연결된 노드가 연결된 노드 집합에 없으면 그 간선을 채택 ( 사이클 체크 )
4. 간선 리스트에 간선이 없을 때까지 반복

코딩 팁 : 엣지 먼저 구현한다

 

from heapdict import heapdict
def prim(graph, start):
	mst, keys, pip, total_weight = list(), heapdict(), dict(), 0
    for node in graph_keys():
    	keys[node] = float('inf')
        pip[node] = none
    keys[start], pip[start] = 0, start

    while keys:
        current_node, current_key = keys, popitem()
        mst.append([pip[current_node], current_node, current_key])
        total_weight += current_key
        for adjacent, weight in mygraph[current_node], items():
            if adjacent in keys and weight < keys[adjacent]:
                keys[adjacent] = weight
                pip[adjacent] = current_node
return mst, total_weight

heapdict() 을 사용하면 pop할때 항상 자동으로 최소값이 갱신된다.