Prim Algorithm

Prim Algorithm

크루스칼이 최소비용 간선을 선택해 나간다면, 프림 알고리즘은 최소비용 간선이 있는 정점을 선택해 나간다.

	시간복잡도
우선순위 큐	O(ElogV)
인접행렬	O(V^2)

구현

import heapq

INF = int(1e9)

def prime(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance[start] = 0

    while queue:
        dist, u = heapq.heappop(queue)

        for v, c in graph[u]:
            if c < distance[v]:
                distance[v] = c

n, m = map(int, input().split()) # 노드, 간선 개수
start = int(input()) # 출발 노드

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

# 간선 정보
for _ in range(m):
    source, dest, cost = map(int, input().split())
    graph[source].append((dest, cost))

prime(start)

print(distance)