Advanced Algorithm - MST(Prim's Algorithm)(5)

1. 프림 알고리즘 코드구현

 

a) 기본그래프 구현

 

- 중복된 간선 정보를 제거한다. 

ex) (7, 'A', 'B')와 (7, 'B', 'A')는 동일하다.

 

myedges = [
    (7, 'A', 'B'), (5, 'A', 'D'),
    (8, 'B', 'C'), (9, 'B', 'D'), (7, 'B', 'E'),
    (5, 'C', 'E'),
    (7, 'D', 'E'), (6, 'D', 'F'),
    (8, 'E', 'F'), (9, 'E', 'G'),
    (11, 'F', 'G')
]

 

b) 프림 알고리즘 로직구현 

1. 그래프의 모든 간선정보를 저장한다. (adjacent_edges)

2. 임의의 노드를 선택하여 '연결된 노드 집합' 이라는 리스트에 삽입한다. (connected_nodes)

3. 2단계에서 선택된 노드에 연결된 간선들을 '간선' 리스트에 삽입한다. (candidate_edge_list / 우선순위 큐) 

4. '간선' 리스트에서 최소 가중치를 가지는 간선부터 추출한다. (간선이 추가될 때마다 가중치를 기준으로 내림차순 정렬)

 - a) '간선' 리스트에서 추출된 노드의 인접노드가 '연결된 노드 집합' 리스트에 이미 존재한다면 스킵한다.(사이클 방지)
 - b) 반대로 존재하지 않는다면, 해당 노드의 간선정보를 '최소신장트리'에 삽입한다.

5. 해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(connected_nodes)' 에 없는 노드와 연결된 간선들만 간선 리스트(candidate_edge_list) 에 삽입

 - a) '연결된 노드 집합(connected_nodes)' 에 있는 노드와 연결된 간선들을 간선 리스트에 삽입해도, 해당 간선은 스킵된다.
 - b) 스킵될 간선을 간선 리스트(candidate_edge_list)에 넣지 않으므로, 간선 리스트(candidate_edge_list)를 최소 가중치 기준으로 다시 정렬하는 불필요한 연산을 줄일 수 있다. (예, 최소힙 구조 사용)

 

6. '간선' 리스트에 더 이상 간선이 없을 때까지 3, 4번 과정을 반복수행한다. 

from collections import defaultdict
from heapq import *

def prim(start_node, edges):
    # mst가 저장될 리스트
    mst = list()
    
    # 어떤 노드와 인접한 노드의 정보를 저장할 리스트 
    adjacent_edges = defaultdict(list) 
    
    # 프림 알고리즘 로직(1)
    for weight, n1, n2 in edges:
        adjacent_edges[n1].append((weight,n1,n2))
        adjacent_edges[n2].append((weight,n2,n1))
    
    # 프림 알고리즘 로직(2)
    connected_nodes = set(start_node)
    
    # 프림 알고리즘 로직(3)
    candidate_edge_list = adjacent_edges[start_node]
    
    # 프림 알고리즘 로직(4)
    heapify(candidate_edge_list)
    
    # 프림 알고리즘 로직(6) 
    while candidate_edge_list:
        
        # 프림 알고리즘 로직(4) 
        weight,n1,n2 = heappop(candidate_edge_list)
        
        # 프림 알고리즘 로직(4 - a)와 (4 - b)
        if n2 not in connected_nodes:
            connected_nodes.add(n2)
            mst.append((weight,n1,n2))
            
            # 프림 알고리즘 로직(5)
            for edge in adjacent_edges[n2]:
                
                # 프림 알고리즘 로직(5 - a)와 (5 - b)
                if edge[2] not in connected_nodes:
                    heappush(candidate_edge_list, edge)
                
    return mst

 

 

[테스트 결과]

위의 결과를 그래프로 표현

 

c) 프림 알고리즘의 시간복잡도

- 최악의 경우, while 구문에서 모든 간선에 대해 반복하고 최소 힙 구조를 사용하므로 O(E log E) 만큼의 시간복잡도를 갖는다.