Prim's algorithm with example

A minimum spanning tree (MST) of a connected weighted undirected graph is a spanning tree with the smallest total edge weight.

Prim's algorithm is a greedy method that grows a single tree from a start vertex. At each step it adds the cheapest edge that connects a vertex in the tree to a vertex outside the tree.

Algorithm

PRIM(G, start)
1. T = {start};  MST edges = empty
2. while T does not contain all vertices
3.     pick the minimum-weight edge (u, v) with u in T and v not in T
4.     add v to T and edge (u, v) to the MST

/* cost[i][j] = weight, INF if no edge */
int prim(int n, int cost[][N]) {
    int total = 0, in[N] = {0};
    in[0] = 1;
    for (int i = 0; i < n - 1; i++) {
        int min = INF, u = -1, v = -1;
        for (int a = 0; a < n; a++) if (in[a])
            for (int b = 0; b < n; b++)
                if (!in[b] && cost[a][b] < min) { min = cost[a][b]; u = a; v = b; }
        in[v] = 1; total += min;
        printf("%d-%d (%d)\n", u, v, min);
    }
    return total;
}

Complexity: O(V²) with a matrix (using a key array), O(E log V) with a heap.

Example

Graph: A-B 2, A-C 6, A-F 7, B-D 11, C-F 3, C-E 5, D-F 9, E-F 1. Start at A.

MST edges: A-B, A-C, C-F, F-E, F-D. Minimum cost = 2 + 6 + 3 + 1 + 9 = 21.