1. 프림 알고리즘(Prim's algorithm): 크루스칼 알고리즘과 다르게(전체 간선을 정렬한 후 하나의 간선부터 시작),
하나의 특정 노드를 정하고, 연결된 간선 중 가중치가 가장 작은 간선을 선택하며 길을 확장하는 알고리즘
(예, 스타 크래프트 게임)
- 크루스칼 알고리즘과 공통점: 둘다 탐욕 알고리즘을 구현함
2. 시간 복잡도: 최악의 경우(while문에서 모든 간선을 돌고, 최소 힙 구조를 이룬다면) O(E logE),
- 개선된 시간 복잡도: O(E logV) <= 보다 많이 사용됨
3. 기본적인 구현
from collections import defaultdict
from heapq import *
def prim(start_node, edges):
mst = list()
# 모든 간선의 정보를 adjacent_egdes에 저장
adjacent_egdes = defaultdict(list)
for weight, n1, n2 in edges:
adjacent_egdes[n1].append((weight, n1, n2))
adjacent_egdes[n2].append((weight, n2, n1))
# 연결된 노드 집합에 시작 노드 포함
connected_nodes = set(start_node)
# 시작(특정) 노드에 연결된 간선 리스트
candidate_edge_list = adjacent_egdes[start_node]
heapify(candidate_edge_list) # 가중치 순으로 간선 리스트 정렬
# 최소 가중치를 가지는 간선부터 추출
while candidate_edge_list:
# 최소 가중치 간선이 추출됨
weight, n1, n2 = heappop(candidate_edge_list)
if n2 not in connected_nodes:
connected_nodes.add(n2)
mst.append((weight, n1, n2))
# n2의 간선들 중
# 연결된 노드 집합에 없는 노드의 간선들만
# 후보 간선 리스트에 추가함
for edge in adjacent_egdes[n2]:
if edge[2] not in connected_nodes:
heappush(candidate_edge_list, edge)
return mst
# 중복된 간선 제외(defaultdict을 이용하기 때문)
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')
]
print(prim('A', myedges))
"""
[(5, 'A', 'D'),
(6, 'D', 'F'),
(7, 'A', 'B'),
(7, 'B', 'E'),
(5, 'E', 'C'),
(9, 'E', 'G')]
"""
4. 개선된 구현
- 간선이 아닌 노드를 중심으로 우선순위 큐를 적용 (간선이 아닌 노드를 핸들링한다고 보면 됨)
- 노드마다 Key 값을 가지고 있고 key 값은 우선순위 큐에 넣는다
"""
heapdict을 쓰는 이유:
새롭게 heap에 push하거나 pop하지 않아도
기존의 heap 내용만 update한다 하더라도
알아서 최소 힙의 구조로 업데이트 함
* heapdict을 쓰기 전에 HeapDict 라이브러리 설치하기:
-> pip install HeapDict
"""
from heapdict import heapdict
# 시간 복잡도: O(E logV) = O(V) + O(V logV) + O(E logV)
def prim(graph, start):
# pi: key를 업데이트하게 하는 상대 노드를 저장
mst, keys, pi, total_weight = list(), heapdict(), dict(), 0
# 초기화: O(V)
for node in graph.keys():
keys[node] = float('inf')
pi[node] = None
keys[start], pi[start] = 0, start
# while문: O(V logV)
while keys:
current_node, current_key = keys.popitem()
mst.append([pi[current_node], current_node, current_key])
total_weight += current_key
# for문: O(E logV)
for adjacent, weight in mygraph[current_node].items():
if adjacent in keys and weight < keys[adjacent]:
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
"""
- 출처 : FASTCAMPUS
댓글