Prim's Algorithm은 그래프에서 MST(최소신장트리)를 찾는 그리디 알고리즘이다.
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight - wikipedia
MST를 만들기 위해 반복해서 vertex를 선택함에 있어서
1. 이미 선택되지 않은 vertex이고 (선택된걸 다시 선택하면 cycle 이 생성되면 트리구조가 깨짐)
2. 가중치를 최소화할 수 있는 vertex
위 조건을 만족하는 가장 작은 edge 가중치로 이어진 vertex를 택한다면 MST를 구성할 수 있다는 알고리즘이다.
매 순간 선택에 있어서 가장 최적의 선택을 한 다는 점에서 그리디 알고리즘의 범주에 들어간다.
보다 자세한 과정은 아래 코드의 주석을 참고 바란다.
# example
V = 5
G = [[0, 9, 75, 0, 0],
[9, 0, 95, 19, 42],
[75, 95, 0, 51, 66],
[0, 19, 51, 0, 31],
[0, 42, 66, 31, 0]]
selected = [0, 0, 0, 0, 0] # 방문한 V는 True, 그렇지 않은 V는 False. 전부 False로 초기화
no_edge = 0 # 몇 개의 edge를 선택했는지
count = 0
selected[0] = True # 어떤 V 부터 방문으로하여 시작할 것인지. 어느 지점으로 시작해도 됨. 0, 1, 2 어떤 수를 넣어도 됨
while (no_edge < V - 1): # 아직 선택하지 않은 edge가 있다면 계속 선택.
minimum = 10e7 # 선택할 수 있는 가중치가 가장 작은 edge를 택하기 위한 기준
x = 0
y = 0
for i in range(V):
if selected[i]: # 각 방문된 V에서 ~
for j in range(V):
count += 1 # 이 j for문 안으로는 몇 번 실행될까요 반목문을 세개나 씀^^;?
if ((not selected[j]) and G[i][j]): # ~ 아직 방문되지 않았고, 가중치가 있어 edge가 존하는 것 중 가장 작은 것을 찾기.
if minimum > G[i][j]:
minimum = G[i][j] # 가장 작은 가중치를 메모
x = i # 가장 작은 가중치 edge의 start
y = j # 가장 작은 가중치 edge의 end
print(str(x) + "-" + str(y) + ":" + str(G[x][y])) # edge의 start, end, 가중치 print
selected[y] = True # start x 는 이미 선택된 V이기에 end를 방문처리해줌
no_edge += 1 # edge가 하나 더 추가되었음.
'''
0-1:9
selected 1 [True, True, 0, 0, 0]
1-3:19
selected 3 [True, True, 0, True, 0]
3-4:31
selected 4 [True, True, 0, True, True]
3-2:51
selected 2 [True, True, True, True, True]
110 # 가중치 결과값
50 # n ** 3 for문이 몇번 실행되었는지 결과값
'''
위 코드의 시간 복잡도는 어떻게 될까?
위 코드에서
while (no_edge < V - 1):
부분은 N번 실행된다. 모든 vertex의 수만큼.
for i in range(V):
각 선택에 있어서 방문되어 있는 vertex를 찾기 위해 for문이 돌아가고,
for j in range(V):
방문되어 있는 vertex에서 아직 방문은 하지않았지만 연결된 vertext 들을 찾는 다고 또 for문이 돌아갔다.
아니 잠깐 뭐가 이상하다. 시간복잡도가 n ** 3 세제곱이라고..?
만족스럽지 않은 결과인데 n의 세제곱이나 나오는 이유는 다음과 같다. 간선의 수를 k라 생각하고
vertex 정점의 수를 n이라고 생각했을때 이 두 관계는 다음과 같다
n - 1 <= k <= n(n-1)/2
즉 n번 각 vertext를 돌면서 각 vertext의 간선을 모두 확인하다보니 썩 그리 맘에 들지는 않는다.
이를 개선하는 방법은, 이미 확인한 간선을 다시 확인하지 않는 것 인데, 자료구조를 생성하여(배열) 메모라이징 방식으로 확인한 간선은 다시 탐색하지 않도록 해주거나, 힙큐를 이용한 방법이 있는데 힙큐방식은 다음과 같다.
힙 큐를 이용하여 vertex에서 연결된 간선들을 넣어주고, 그 다음 vertex 를 찾은 뒤에는 또 새로 연결된 간선들을 찾아주면서 최소한의 간선들만 택하는 방식을 사용하면 매번 for문들 돌면서 중복된 간선을 또 확인할 필요가 없어진다.
힙큐로 인해 가장 최소의 가중치를 찾기 위한 for문이 아닌 최소힙으로 도출해내어 더 좋은 효율을 얻을 수 있다.
def prim(graph, start_node):
visited[start_node] = 1 # 방문 갱신
candidate = graph[start_node] # 인접 간선 추출
heapq.heapify(candidate) # 우선순위 큐 생성
mst = [] # mst
total_weight = 0 # 전체 가중치
while candidate:
weight, u, v = heapq.heappop(candidate) # 가중치가 가장 적은 간선 추출
if visited[v] == 0: # 방문하지 않았다면
visited[v] = 1 # 방문 갱신
mst.append((u,v)) # mst 삽입
total_weight += weight # 전체 가중치 갱신
for edge in graph[v]: # 다음 인접 간선 탐색
if visited[edge[2]] == 0: # 방문한 노드가 아니라면, (순환 방지)
heapq.heappush(candidate, edge) # 우선순위 큐에 edge 삽입
return total_weight
어느 vertex를 선택하여 시작을 하건간에 매번 선택할 때마다 최소 간선으로 연결된 vertex를 선택하면 어떻게 MST가 도출되는걸까?
MST Lemma(부명제):
A가 그래프 G의 spanning tree라고 하자. e(b) 는 A에 속하지 않은 G의 edge이다.
위 1, 2 조건을 만족시키면서
MST의 한 부분인 T에다가 방문하지 않은 최소 edge vertex 하나를 붙이더라도 해당 edge가 추가된 T는 MST 속성이 유지된다. 즉 3번, 가중치가 낮은 것을 더했기에 결과도 가중치가 낮다고 할 수 있다.
자꾸 같은 표현을 반복하는 것 같은데 정리하자면,
매 선택에 있어서 방문했던 vertex를 선택을 피하기에 cycle이 형성되지 않고, 매 선택에서 가중치가 가장 낮은 edge를 선택해왔기에 그 결과물의 그래프 또한 가중치는 낮으면서 cycle이 형성되지 않은 MST트리의 조건을 충족시킨다.