Prim's Algorithm Algorithm Tutorial

Prim's Algorithm

Prim's Algorithm builds the Minimum Spanning Tree (MST) by growing from a starting vertex. You repeatedly add the minimum weight edge connecting the tree to an unvisited vertex.

Unlike Kruskal, Prim's works better on dense graphs because you don't need to sort all edges upfront.

function prim(graph, n):
    visited = array of size n, initialized to false
    pq = min-priority queue
    pq.push((0, 0))
    mstWeight = 0
    edgesUsed = 0

    while pq is not empty and edgesUsed < n:
        (weight, u) = pq.pop()
        if visited[u]:
            continue
        visited[u] = true
        mstWeight = mstWeight + weight
        edgesUsed = edgesUsed + 1

        for each edge (u, v, w) from u:
            if not visited[v]:
                pq.push((w, v))

    if edgesUsed != n:
        return -1
    return mstWeight

Prim vs Kruskal: Prim works better on dense graphs. Kruskal works better on sparse graphs where sorting fewer edges is faster.

Skip optimization: When you pop a vertex from the queue, skip it if already visited.

Applications: You use Prim for network cable layout, circuit design, maze generation, and hierarchical clustering.

Time complexity: $O((V + E) \log V)$ with a binary heap.

Space complexity: $O(V + E)$ for the graph and priority queue.