DSA — Prim's Algorithm

What is Prim's Algorithm?

Finds MST by growing from a starting vertex, always adding the cheapest edge.

import heapq

def prim(graph, start=0):
    n = len(graph)
    visited = [False] * n
    mst = []
    pq = [(0, start, -1)]
    
    while pq:
        weight, u, parent = heapq.heappop(pq)
        
        if visited[u]:
            continue
        
        visited[u] = True
        if parent != -1:
            mst.append((parent, u, weight))
        
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (w, v, u))
    
    return mst

Time Complexity

Operation	Complexity
Using priority queue	O(E log V)
Using adjacency matrix	O(V²)

Applications

• Network design
• Cable wiring
• Road network planning

Mini Practice

1. Implement Prim's algorithm
2. Find minimum spanning tree
3. Compare with Kruskal's
4. Handle disconnected graphs

Up Next

Continue with Topological Sort — ordering directed graphs.