[CLRS] [21-2] Prim Algorithms

1. Prim's Algorithm?

- MST를 구현하기위해 사용되는 알고리즘 중 하나이다.

- 매순간 최선의 조건을 선택하는 Greedy Algorithms중 하나라고 생각하면 좋다.

- 연결된 인접 정점들 중 가장 비용이 적은 엣지로 연결된 노드을 선택한다.

'''

1. 시작 노드를 MST에 삽입한다.

2. MST의 속한 노드들과 인접한 노드들 중 가장 낮은 가중치의 엣지와 연결된 노드에 대해 엣지와 노드를 MST에 넣는다.

--> cycle을 막기위해 연결된 노드가 MST에 속하면 다음 노드를 판단한다.

3. 2번 과정을 계속 반복한다. (노드수가 Graph의 노드수와 같아질때까지)

'''

2. Prim Algorithms 구현 

- 노드와 노드간의 최솟값을 탐색하기위해 우선순위 Queue를 사용하여

- 효과적으로 구현해보고자 한다.

from heapq import heappush
from heapq import heappop

def Prim(graph,graph_v,start):
    return_list = []
    h = list()
    connect = list()
    for i in range(len(graph)):
        connect.append(False)
    heappush(h,(0,start))
    total_weight = 0
    vertex_count = 0

    while vertex_count < len(graph):
        pop_info = heappop(h)
        pop_weight = pop_info[0]
        pop_node = pop_info[1]
        if connect[pop_node] == False:
            connect[pop_node] = True
            total_weight += pop_weight
            vertex_count += 1
            return_list.append(graph_v[pop_node])
            for i in range(0,len(graph)):
                if (graph[pop_node][i] != 0) and (connect[i] == False):
                    heappush(h,(graph[pop_node][i],i))
    return return_list,total_weight

G = [[0,4,0,0,0,8,0],
     [4,0,6,0,0,11,0],
     [0,6,0,7,0,0,2],
     [0,0,7,0,14,0,0],
     [0,0,0,14,0,2,1],
     [8,11,0,0,2,0,7],
     [0,0,2,0,1,7,0]]

V = ['A','B','C','E','F','G','H']

print(Prim(G,V,0))

--------------------------------------------------------
Output 

(['A', 'B', 'C', 'H', 'F', 'G', 'E'], 22)