[코딩 + 알고리즘 완주반] 23일차. 최소 신장 트리 - 프림 알고리즘 (Prim's algorithm)

# 프림 알고리즘

시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방법

( 크루스칼 알고리즘은 전체에서 가장 작은 간선)

 

1. 임의의 정점을 선택하여 연결된 노드 집합에 삽입

2. 선택한 정점에 연결된 간선들을 간선 리스트에 삽입

3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서 ( 전에 넣었던 간선들 포함 간선리스트에서 가장 최소인 값 )

      - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 이미 있다면 skip (cycle 방지)

      - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 있지 않다면 해당 간선을 선택 ( 최소신장트리에 삽입 )

          (해당 간선에 연결된 정점의 간선들 중 연결된 노드 집합에 없는 노드와 연결된 간선들만 간선리스트에 삽입)

4. 추출한 간선은 간선 리스트에서 제거

5. 간선 리스트에 더 이상 간선이 없을 때까지 반복

 

# 알고리즘 구현

heapq 라이브러리 활용 우선순위 큐 사용

# heapq.heappush(), heappop() 활용
import heapq

queue = []
graph_data = [[2, 'A'], [5, 'B'], [3, 'C']]

for edge in graph_data:
    heapq.heappush(queue, edge)
    
for index in range(len(queue)):
    print (heapq.heappop(queue))

print (queue)

# 2. heapq.heapify() 함수 활용
import heapq

graph_data = [[2, 'A'], [5, 'B'], [3, 'C']]

heapq.heapify(graph_data) # 인덱스 0 기준
    
for index in range(len(graph_data)):
    print (heapq.heappop(graph_data))

print (graph_data)

 

프림 알고리즘 코드 구현

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')
]

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))

    connected_nodes = set(start_node) # 연결된 노드 집합
    candidate_edge_list = adjacent_edges[start_node] # 연결된 간선 집합
    heapify(candidate_edge_list)
    
    while candidate_edge_list:
        weight, n1, n2 = heappop(candidate_edge_list) # 가중치 작은 간선부터 pop
        if n2 not in connected_nodes: # 연결된 노드 집합에 없으면 mst에 삽입
            connected_nodes.add(n2)
            mst.append((weight, n1, n2))
            
            for edge in adjacent_edges[n2]: # 간선에 연결된 정점 중 연결된 노드 집합에 없는 정점의 간선들만 간선리스트에 삽입
                if edge[2] not in connected_nodes:
                    heappush(candidate_edge_list, edge)

    return mst

최악의 경우 시간 복잡도 O(ElogE)

 

# 개선된 프림 알고리즘

heapdict 라이브러리 사용하여 간선이 아닌 노드 중심으로 우선순위 큐 적용

1. 초기화 

   정점 : key 구조를 만들어 놓고, 특정 정점의 key 값은 0, 이외의 정점들의 key 값은 무한대로 설정 후 우선순위 큐에 삽입

2. Extract min 로직

   가장 key 값이 작은 정점과 key를 pop

3. Decrease Key 로직

   해당 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key 값이 작으면 해당 정점 : key 값을 갱신

     - 갱신 시, 우선순위 큐는 최소 key 값을 가지는 정점 : key 를 루트 노드로 올려 놓도록 재구성

 

from heapdict import heapdict

def prim(graph, start):
    mst, keys, pi, total_weight = list(), heapdict(), dict(), 0
    for node in graph.keys():
        keys[node] = float('inf')
        pi[node] = None
    keys[start], pi[start] = 0, start

    while keys:
        current_node, current_key = keys.popitem() # key값이 가장 작은 노드 pop
        mst.append([pi[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]: # key값에는 아직 선택받지 못한 key들만 들어있음, 키값보다 가중치가 더 작다면 키값 업데이트
                keys[adjacent] = weight
                pi[adjacent] = current_node # 업데이트 영향 받은 노드 저장 (업데이트한 간선에 연결된 노드)
    return mst, total_weight

mygraph = {
    'A': {'B': 7, 'D': 5},
    'B': {'A': 7, 'D': 9, 'C': 8, 'E': 7},
    'C': {'B': 8, 'E': 5},
    'D': {'A': 5, 'B': 9, 'E': 7, 'F': 6},
    'E': {'B': 7, 'C': 5, 'D': 7, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}    
}
mst, total_weight = prim(mygraph, 'A')
print ('MST:', mst)
print ('Total Weight:', total_weight)

MST: [['A', 'A', 0], ['A', 'D', 5], ['D', 'F', 6], ['A', 'B', 7], ['D', 'E', 7], ['E', 'C', 5], ['E', 'G', 9]]

Total Weight: 39

 

# 개선된 프림 알고리즘의 시간 복잡도 : O(ElogV)

최초 key 생성 시간 복잡도 O(V)

while 문, key.popitem() 의 시간 복잡도 O(VlogV)

for 문 총 시간 복잡도  O(ElogV)

총 시간 복잡도는 O(V+VlogV + ElogV)

 ->  E>V 이므로 O(ElogV)로 나타낼 수 있음