프림 알고리즘에 대해 알아보자

최소 신장 트리(MST: Minimal Spanning Tree)

• 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리

• 도로망 설계, 전기 회로 설계, 네트워크 연결, 센서 네트워크 설치 등에서 최소 비용으로 모든 노드를 연결하고자 할 때 흔히 사용

• 이러한 최소 신장 트리를 찾아내는 알고리즘에는 대표적으로 프림 알고리즘(Prim Algorithm)과 크루스칼 알고리즘(Kruskal)이 있다.

프림 알고리즘(Prim Algorithm)

• 프림 알고리즘은 그리디 알고리즘을 통해 MST를 찾아내는 알고리즘으로, 다음과 같이 동작한다.

시작 노드 선택: 그래프의 임의의 노드를 시작 노드로 선택합니다. 이 시작 노드는 최소 신장 트리의 일부가 되며, 알고리즘의 시작점입니다.

초기화: 시작 노드에서부터 연결된 간선들을 고려하여 인접한 노드들 중에서 아직 최소 신장 트리에 포함되지 않은 노드를 선택하고, 해당 간선의 가중치를 기준으로 우선순위 큐(Priority Queue)에 삽입합니다. 이때, 최소 신장 트리에 포함된 노드들은 '방문한 노드'로 표시합니다.

반복: 우선순위 큐에서 가장 작은 가중치를 가진 간선을 선택합니다. 이 간선으로 연결된 노드들 중에서 최소 신장 트리에 포함되지 않은 노드를 선택하고, 해당 간선의 가중치를 기준으로 우선순위 큐에 삽입합니다. 이때, 선택된 노드를 '방문한 노드'로 표시합니다. 이 과정을 반복하여 모든 노드들이 최소 신장 트리에 포함될 때까지 진행합니다.

종료 조건: 모든 노드들이 최소 신장 트리에 포함되면 알고리즘을 종료합니다.

최소 신장 트리 구성: 최소 신장 트리에 포함된 간선들을 선택하여 최소 신장 트리를 구성합니다.

• 출처: 내 친구 GPT

프림 알고리즘의 장점

프림 알고리즘은 특정 노드에서 시작하여 그래프를 확장해가는 방식으로 동작하므로, 그래프가 밀집된 경우(간선 수가 노드 수에 가까운 경우)에 더 효율적으로 동작할 수 있다 !!

• 코드도 보면서 이해해보자.

import sys
import heapq

input = sys.stdin.readline

V, E = list(map(int, input().split()))
edges = [[] for _ in range(V + 1)]  # 각 노드의 연결된 간선들을 저장할 리스트
for _ in range(E):
    u, v, w = list(map(int, input().split()))
    edges[u].append((v, w))
    edges[v].append((u, w))

visited = set()  # 이미 선택된 노드들을 저장할 set
choosedEdges = []  # 선택된 간선들을 저장할 리스트
start_node = 1  # 시작 노드를 임의로 1로 선택
visited.add(start_node)

# 시작 노드와 연결된 간선들을 우선순위 큐에 추가
pq = [(w, v, start_node) for v, w in edges[start_node]]
heapq.heapify(pq)
while pq:
    # 가장 가중치가 작은 간선을 선택
    weight, v, u = heapq.heappop(pq)
    if v not in visited:
        visited.add(v)
        choosedEdges.append((u, v, weight))
        for nv, nw in edges[v]:
            # 방문하지 않은 노드들 중에서 연결된 간선들을 우선순위 큐에 추가
            if nv not in visited:
                heapq.heappush(pq, (nw, nv, v))
                print(pq)

print(sum([weight for u, v, weight in choosedEdges]))

생각보다 코드 자체의 흐름은 복잡하지 않아 이해하기 어렵지 않았다. 다만 코드를 읽는 중 생긴 의문점을 해소하는 데에 꽤나 오랜 시간이 걸렸다. 의문점은 다음과 같다.

• A는 초기에 정한 노드이다. 이후 A 노드와 B노드를 연결하는 간선 a가 있다고 가정하자. 하지만 a의 가중치가 높아 프림 알고리즘의 우선순위에서 밀렸고, 다른 노드들과의 연결이 먼저 이루어졌다. 이후 몇번의 반복 이후, A와 B노드는 스패닝 트리를 이루게 되었다.(ex. A-C-D-B) 그렇다면 기존의 a간선은 효력을 잃고 삭제되어야 하는거 아닌가? 왜 이러한 부분이 안보이지?!?!

답은 간단했다. 이 코드는 결과적으로 모든 노드를 다 들여다 보게 작성되어있다. 효력을 잃는다고 삭제할 필요가 없다. 왜냐하면

if v not in visited:

이 부분에서 효력을 잃은 간선들은 if문 내부로 들어가질 못하고 힙에서 삭제된다. ㅋㅋㅋㅋ... 생각보다 별 이유 아니여서 김빠짐