최소 신장 트리 - 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 등의 함수 호출 때문에 시간이 훨씬 더 많이 걸린다. 노드의 수가 많다면 반복문을 이용하는 것이 좋다.