최소 신장 트리 - Prim's algorithm

최소 신장 트리 - Prim's algorithm

프림 알고리즘 (Prim's Algorithm)

시작 정점을 선택한 후, 정점에 연결된 간선 중 최소 비용으로 연결된 정점을 선택한다. 또 간선으로 연결된 정점들 중에서 최소 간선으로 연결된 정점을 하나씩 선택해가며 최소 신장 트리(Minimal Spannin Tree)를 만들어가는 알고리즘.

A를 시작 정점으로 선택하면 정점에 5, 6, 10 의 비용을 가진 간선들 중 하나를 선택할 수 있다. 이 중 최소비용을 가진 5의 간선을 선택하면, F와 연결된 7 비용의 간선과 남은 6, 10 의 비용을 가진 간선 중 하나를 선택할 수 있다.

7, 6, 10 중 6의 간선 비용이 가장 최소 비용이므로 A와 C를 연결 해준다. 또 C를 기준으로 11, 3, 30 의 간선을 갈 수 있게 되며 이전에 남은 간선들과 새로운 간선들 중 3의 비용을 가진 간선이 가장 최소이므로 또 연결 해준다.

남은 간선들을 기준으로 최소 비용 간선을 찾으면 E-F 간선이나, 이는 cycle을 형성하므로 그다음으로 최소 비용이 드는 E-B 간선을 선택한다. cycle이 형성되는 간선을 모두 제외하고 나면 아래와 같이 최소 신장 트리가 완성 된다.

이는 우선 순위 큐(heapq)를 이용하거나, 거리 정보를 저장하는 리스트를 이용하여 구현할 수 있다.

거리 정보 리스트를 이용한 반복문 구현

거리 정보 저장을 인접 행렬 혹은 인접 리스트로 구현할 수 있는데, 인접 리스트의 경우 append 연산을 사용하기 때문에 데이터 저장 시 시간이 오래 걸리므로 인접 행렬을 이용하는 것이 좋다.

def prim(start, adj): INF = 0xffffffffff dist = adj[start][:] # 시작 점을 기준으로 거리 저장 ans = 0 team = [0]*V # 이미 선택된 정점인지 확인 (cycle 방지) for _ in range(V): min_d = INF min_v = 0 for i in range(V): # 모든 정점을 돌며 최소 비용 간선(정점) 정보를 저장 if dist[i] < min_d and not team[i]: min_d = dist[i] min_v = i team[min_v] = 1 # 최소 비용 간선 선택 ans += min_d # 최소 비용에 추가 for i in range(V): # 추가된 정점을 기준으로 거리 갱신 if dist[i] > adj[min_v][i] and not team[i]: dist[i] = adj[min_v][i]

우선 순위 큐 (힙 큐) 를 이용한 구현

이번에도 간선 정보 저장은 인접행렬을 이용하였다.

import heapq def prin(start): INF = 0xffffffff q = [] heapq.heappush(q, (start, 0)) #시작점부터 heapq에 저장. 비용을 기준으로 정렬되도록 함 ans = 0 team = [0]*V while q: # q가 빌 때까지 (모든 정점 확인) w, node = heapq.heappop(q) # 가장 비용이 적은 간선과 정점 pop if team[node]: # 만약 이미 연결되어 있다면 continue continue team[node] = 1 # 간선 연결 ans += w for i in range(V): # 방금 연결한 정점과 이어진 간선들 heapq에 push if not team[i] and adj[node][i] < INF: heapq.heappush(q, (adj[node][i], i))

heapq가 좀더 직관적이지만, pop, push 등의 함수 호출 때문에 시간이 훨씬 더 많이 걸린다. 노드의 수가 많다면 반복문을 이용하는 것이 좋다.

from http://amaranth1ne.tistory.com/34 by ccl(A) rewrite - 2021-10-16 22:26:05