Kruskal and Prim

Why it exists

The cut property (spanning trees) says which edges are safe; this page says how to find them quickly. Kruskal's algorithm looks at the edges in order of weight and keeps those that do not close a cycle, using a disjoint-set structure to test cycles fast. Prim's algorithm grows one tree from a start vertex, always adding the cheapest edge that leaves the tree, using a priority queue (the same idea as Dijkstra's algorithm). GATE asks for the edges in the order they are added, the total weight, which algorithm suits which graph, and the exact running times.

Prerequisites

You need the cut property and spanning trees (spanning trees and the cut property); for Prim's heap version the binary heap (binary heap).

Precise definitions

Disjoint-set (union-find) structure. It keeps a partition of $n$ elements into sets and supports make-set, find$(x)$ (the representative of the set containing $x$) and union$(a, b)$ (merge the two sets). Each set is a tree of parent pointers; the root is the representative. Two heuristics: union by rank (attach the shallower tree below the root of the deeper one) keeps the height at most $\log_2 n$; path compression (in find, point every node on the path directly at the root) flattens the trees. With both, a sequence of $m$ operations on $n$ elements takes $O(m\,\alpha(n))$ time, where $\alpha$ is the inverse Ackermann function, below $5$ for every practical $n$: effectively constant.

Kruskal's algorithm. Sort the edges by weight. Make each vertex a set. For each edge $(u, v)$ in order: if $\text{find}(u) \ne \text{find}(v)$, add the edge to the tree and union the two sets; otherwise skip it (it would close a cycle). Stop after $V - 1$ edges.

Prim's algorithm. Pick a root. Keep for every vertex $v$ outside the tree a $\text{key}[v]$: the weight of the cheapest edge joining $v$ to the tree (infinity if none), and $\text{parent}[v]$ the tree end of that edge. Repeatedly take the vertex $u$ outside the tree with the smallest key, add it (and the edge to its parent) to the tree, and for each neighbour $v$ outside the tree with $w(u, v) < \text{key}[v]$ set $\text{key}[v] = w(u, v)$ and $\text{parent}[v] = u$.

How it works

Kruskal, step by step

The graph has $7$ vertices and $11$ edges, listed here in order of weight: $(1,2)=2$, $(3,4)=3$, $(0,1)=4$, $(4,5)=5$, $(2,3)=6$, $(5,6)=7$, $(1,3)=8$, $(0,2)=9$, $(2,4)=10$, $(4,6)=11$, $(3,5)=12$. The animation is the real code including the union-find; the row "the set of each vertex" shows the root of each vertex's tree, so you can see the sets merge.

The first six edges are accepted (each joins two different trees); after the sixth, edge $(5, 6)$ with weight $7$, there is one tree of $6$ edges and weight $27$, and the remaining five edges all have both ends in the same tree and are rejected. A spanning tree of $7$ vertices has exactly $6$ edges, so the algorithm can stop as soon as it has accepted $V - 1$ edges.

Correctness. When Kruskal accepts $(u, v)$, $u$ and $v$ are in different trees $T_u$ and $T_v$ of the current forest. Take the cut $(V(T_u), \text{rest})$: it respects the chosen edges, and the edge $(u, v)$ crosses it. Every edge lighter than $(u, v)$ was looked at earlier and either was chosen (then it lies inside a tree, not across this cut) or was rejected (both ends in the same tree); so $(u, v)$ is the lightest crossing edge, i.e. light, hence safe by the cut property.

Running time. Sorting: $O(E \log E)$. The loop: $E$ find operations and at most $V - 1$ unions: $O(E\,\alpha(V))$, which is dominated by the sort. Since $E \le V^2$ we have $\log E \le 2 \log V$, so $O(E \log E) = O(E \log V)$. If the edges are already sorted (or can be sorted by counting sort because weights are small integers) the rest is nearly linear.

Prim, step by step

The same graph, as a weight matrix, from vertex $0$. The animation shows the in-tree flags, the keys (blank = infinity) and the parents.

Vertex $0$ joins with key $0$; its neighbours $1$ and $2$ get keys $4$ and $9$. The cheapest outside vertex is $1$ (key $4$); that lowers the key of $2$ to $2$ (via the edge $(1, 2)$) and gives $3$ the key $8$. Then $2$ (key $2$), which lowers the key of $3$ to $6$; then $3$ (key $6$), then $4$ (key $3$), $5$ (key $5$) and $6$ (key $7$): total $4 + 2 + 6 + 3 + 5 + 7 = 27$. Prim added the edges in a different order from Kruskal but chose the same tree (all weights are distinct, so the MST is unique).

Correctness. At each step the cut $(\text{tree}, \text{rest})$ respects the chosen edges, and Prim adds the lightest edge crossing it: safe by the cut property.

Running time depends on the data structure for the keys.

With a heap, each vertex is extracted once ($V$ extractions of $O(\log V)$) and each edge may lower a key once ($E$ decrease-key operations of $O(\log V)$ in a binary heap).

Which to use

• Sparse graph ($E$ about $V$): both are $O(V \log V)$; Kruskal is simplest if the edges come as a list.
• Dense graph ($E$ about $V^2$): Prim with an array and a matrix, $O(V^2)$, beats Kruskal's $O(V^2 \log V)$.
• Kruskal works on a forest (disconnected graph) and returns a minimum spanning forest; Prim as written needs a connected graph (or a restart for each component).

Both agree

The program runs both algorithms, on the page graph and on $2000$ random connected graphs with $8$ vertices and random weights from $1$ to $20$ (so there are many ties), and compares the total weights.

#include <stdio.h>
#include <stdlib.h>
 
#define MAXN 12
#define INF 1000000
 
struct edge { int u, v, w; };
 
static int parent_[MAXN], rank_[MAXN];
static int find(int x) { if (parent_[x] != x) parent_[x] = find(parent_[x]); return parent_[x]; }
static int unite(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return 0;
    if (rank_[ra] < rank_[rb]) { int t = ra; ra = rb; rb = t; }
    parent_[rb] = ra;
    if (rank_[ra] == rank_[rb]) rank_[ra]++;
    return 1;
}
static int by_weight(const void *a, const void *b) { return ((const struct edge *)a)->w - ((const struct edge *)b)->w; }
 
/* Kruskal: n vertices, m edges; returns the weight of a minimum spanning tree */
static int kruskal(int n, struct edge e[], int m) {
    int total = 0;
    qsort(e, (size_t)m, sizeof e[0], by_weight);
    for (int v = 0; v < n; v++) { parent_[v] = v; rank_[v] = 0; }
    for (int i = 0; i < m; i++) if (unite(e[i].u, e[i].v)) total += e[i].w;
    return total;
}
 
/* Prim from vertex 0 on a weight matrix (0 = no edge) */
static int prim(int n, int w[MAXN][MAXN]) {
    int key[MAXN], in_tree[MAXN] = {0}, total = 0;
    for (int v = 0; v < n; v++) key[v] = INF;
    key[0] = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int v = 0; v < n; v++) if (!in_tree[v] && (u == -1 || key[v] < key[u])) u = v;
        in_tree[u] = 1;
        total += key[u];
        for (int v = 0; v < n; v++) if (w[u][v] && !in_tree[v] && w[u][v] < key[v]) key[v] = w[u][v];
    }
    return total;
}
 
int main(void) {
    struct edge e[11] = {{0, 1, 4}, {0, 2, 9}, {1, 2, 2}, {1, 3, 8}, {2, 3, 6}, {2, 4, 10}, {3, 4, 3}, {3, 5, 12}, {4, 5, 5}, {4, 6, 11}, {5, 6, 7}};
    int w[MAXN][MAXN] = {{0}};
    for (int i = 0; i < 11; i++) { w[e[i].u][e[i].v] = e[i].w; w[e[i].v][e[i].u] = e[i].w; }
    printf("page graph: Kruskal %d, Prim %d\n", kruskal(7, e, 11), prim(7, w));
    unsigned s = 20240601;
    int agree = 0, trials = 2000, edges_total = 0;
    for (int t = 0; t < trials; t++) {                          /* random connected graphs on 8 vertices, random weights (ties allowed) */
        int n = 8, m = 0;
        struct edge g[64];
        int mat[MAXN][MAXN] = {{0}};
        for (int v = 1; v < n; v++) {                           /* a random tree first, so the graph is connected */
            s = s * 1103515245u + 12345u;
            int u = (int)((s >> 8) % (unsigned)v);
            s = s * 1103515245u + 12345u;
            int wt = 1 + (int)((s >> 8) % 20);
            mat[u][v] = mat[v][u] = wt;
        }
        for (int k = 0; k < 10; k++) {                          /* then some more edges */
            s = s * 1103515245u + 12345u;
            int u = (int)((s >> 8) % n);
            s = s * 1103515245u + 12345u;
            int v = (int)((s >> 8) % n);
            s = s * 1103515245u + 12345u;
            int wt = 1 + (int)((s >> 8) % 20);
            if (u != v && !mat[u][v]) mat[u][v] = mat[v][u] = wt;
        }
        for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++) if (mat[u][v]) { g[m].u = u; g[m].v = v; g[m].w = mat[u][v]; m++; }
        edges_total += m;
        if (kruskal(n, g, m) == prim(n, mat)) agree++;
    }
    printf("random connected graphs on 8 vertices: Kruskal and Prim gave the same weight in %d of %d (average %d edges)\n", agree, trials, edges_total / trials);
    return 0;
}

page graph: Kruskal 27, Prim 27
random connected graphs on 8 vertices: Kruskal and Prim gave the same weight in 2000 of 2000 (average 12 edges)

The weights always agree. With tied weights the trees may differ (several MSTs exist) and so can the order in which edges are added.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Both algorithms apply the cut property of spanning trees as a greedy algorithm; Prim's heap version uses the binary heap and is almost the same code as Dijkstra's algorithm (the key is an edge weight instead of a path length).

PYQs

The number of distinct minimum-weight spanning
trees of the following graph is
.

Consider a graph G = (V, E), where V = {v 1 , v 2 ,
..., v 100 }, E = {(v i , v j ) | 1 <= i <= j <= 100}, and
weight of the edge (v i , v j ) is |i – j|. The weight of
the minimum spanning tree of G is   .
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !
5

The graph shown below has 8 edges with distinct
integer edge weights. The minimum spanning
tree (MST) is of weight 36 and contains the edges:
{(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge
weights of only those edges which are in the MST
are given in the figure shown below. The
minimum possible sum of weights of all 8 edges
of this graph is

An undirected graph G(V,E) contains n (n > 2)
nodes named v1, v2... vn. Two nodes vi , vj are
connected if and only if 0 < | i- j | < = 2 . Each
edge ( vi, vj )is assigned a weight i + j. A sample
graph with n = 4 is shown below.

What will be the cost of the minimum spanning
tree (MST) of such a graph with 11 nodes?

An undirected graph G(V, E) contains n (n > 2)
nodes named v1, v2, . . . , vn. Two nodes vi, vj are
connected if and only if 0 < |i - j| ≤ 2. Each edge
(vi, vj) is assigned a weight i + j. A sample graph
with n = 4 is shown below.

The length of the path from v5 to v6 in the
MST of previous question with n = 10 is

Consider a complete undirected graph with vertex
set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below
is the weight of the edge {i, j}.

0
1
8
1 4
l1
0
12
4 9
W = ⎪8 12
0
7 3⎪
1
4
7
0 2
h4
9
3
2 0)
What is the minimum possible weight of a spanning
tree T in this graph such that vertex 0 is a leaf node
in the tree T?

Consider the following graph:

Which one of the following is NOT the
sequence of edges added to the minimum
spanning tree using Kruskal's algorithm?

For the undirected, weighted graph given below,
which of the following sequences of edges
represents a correct execution of Prim's algorithm
to construct a Minimum Spanning Tree?

Consider the following graph:

Which one of the following cannot be the sequence of
edges added, in that order, to a minimum spanning
tree using Kruskal's algorithm?

Self-check

Revision card

References