Prim’s Algorithm

Prim’s Algorithm is another approach to find the minimum spanning tree (MST) from a given graph.

Its code implementation is simpler and easier than Kruscal’s Algorithm based on union-find.

Key Idea

• Grow the MST greedily: Pick the smallest edge that connects a visited node to an unvisited node.
• Priority queue (min-heap): Use min-heap to efficiently pick the smallest edge.
• Repeat until all nodes are included.

Code Implementation

Assume the input is given as A, B, and C, representing the edge between node A and node B with weight C.

import heapq
import sys
input = sys.stdin.readline

v, e = map(int, input().split())

edges = [[] for _ in range(v + 1)]
for _ in range(e):
    a, b, c = map(int, input().split())
    edges[a].append((c, b))
    edges[b].append((c, a))

visited = [False] * (v + 1)
heap = [(0, 1)]
result = 0
while heap:
    cost, next_node = heapq.heappop(heap)
    if not visited[next_node]:
        visited[next_node] = True
        result += cost
        for next_edge in edges[next_node]:
            if not visited[next_edge[1]]:
                heapq.heappush(heap, next_edge)

print(result)