Prim's MST

Graphs O(V²) O(V)

Grows a minimum spanning tree from a start node, always adding the cheapest edge that reaches a new node.

Start node

1/23

Start from 0: key[0] = 0, all others ∞.

InvariantThe chosen edges form one tree, and each was the cheapest edge leaving it — the cut property makes that safe.

currentfrontiervisitedtree edge

prim.c

#define V 6
#define INF 1000000
 
void prim(int graph[V][V], int start) {
    int inMST[V] = {0};
    int key[V], parent[V];
    for (int i = 0; i < V; i++) key[i] = INF;
    key[start] = 0;
 
    for (int count = 0; count < V; count++) {
        int u = -1;
        for (int v = 0; v < V; v++)
            if (!inMST[v] && (u == -1 || key[v] < key[u]))
                u = v;
        inMST[u] = 1;
 
        for (int v = 0; v < V; v++)
            if (graph[u][v] && !inMST[v] &&
                graph[u][v] < key[v]) {
                key[v] = graph[u][v];
                parent[v] = u;
            }
    }
}

How Prim's MST works

Grow one tree from a start node: at each step add the cheapest edge that connects the tree to a new node. The cheapest crossing edge is always safe to take.

Worst case

O(V²) with the array scan shown here; O(E log V) with a heap.

When to use it

Minimum spanning tree on dense graphs, or when you want the tree to grow from a specific node.