36.06Intermediate / Advanced4 topics15 min3 interactive animations

MST correctness

Why the greedy algorithms are right: the exchange argument, the cut argument, the safe-edge choice at every step, and a comparison of what each algorithm costs.

Learning goals

State the optimality condition of a spanning tree in terms of cycles
State it in terms of cuts
Explain why each greedy step is safe
Choose between Kruskal, heap Prim and array Prim from n and m

Prerequisites

MST definitionsKruskal's algorithmPrim's algorithm

A greedy algorithm that always grabs the cheapest option usually fails. Spanning trees are a famous case where it works, and the reason is two clean facts about exchanging one edge for another.

36.06.1

Exchange proof

**Exchange argument.** A spanning tree T is minimum if and only if, for every non-tree edge e, w(e) is at least the weight of every edge on the tree path between its ends. If some tree edge on that path were heavier than e, exchanging them would give a lighter spanning tree, a contradiction; and if no exchange helps, no sequence of exchanges does, because any spanning tree can be turned into any other by single swaps.

The check below is exactly that condition, and it is used as a test for any tree you want to verify. The *Cycle property* animation option runs it for each rejected edge of Kruskal's tree.

Java

1static boolean isMinimumSpanningTree(int n, int[][] edges, int[] tree) {   // tree = indexes of n - 1 edges
2    if (tree.length != n - 1) return false;
3    int[] parent = new int[n];
4    for (int i = 0; i < n; i++) parent[i] = i;
5    boolean[] inTree = new boolean[edges.length];
6    List<int[]>[] adj = new List[n];
7    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
8    for (int k : tree) {
9        if (inTree[k]) return false;
10        int a = find(parent, edges[k][0]), b = find(parent, edges[k][1]);
11        if (a == b) return false;                                      // not even a tree
12        parent[a] = b;
13        inTree[k] = true;
14        adj[edges[k][0]].add(new int[]{edges[k][1], edges[k][2]});
15        adj[edges[k][1]].add(new int[]{edges[k][0], edges[k][2]});
16    }
17    for (int k = 0; k < edges.length; k++)
18        if (!inTree[k] && maxOnPath(adj, edges[k][0], edges[k][1], -1) > edges[k][2]) return false;   // swapping k in gives a lighter tree
19    return true;
20}
21static int maxOnPath(List<int[]>[] tree, int u, int target, int from) {
22    if (u == target) return 0;
23    for (int[] e : tree[u]) {
24        if (e[0] == from) continue;
25        int sub = maxOnPath(tree, e[0], target, u);
26        if (sub >= 0) return Math.max(sub, e[1]);
27    }
28    return -1;
29}
30static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

MST properties and variations: cut, cycle, second best, critical edges

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Being examinedIn the minimum spanning treeSide S of the cutHeaviest edge on the path (the swap)Not in the tree

side S

Setup

A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.

Step 1 / 3

Java

1static long secondBestMst(int n, int[][] edges) {   // connected graph; Long.MAX_VALUE when no other spanning tree exists
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    boolean[] inTree = new boolean[sorted.length];
7    List<int[]>[] tree = new List[n];
8    for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
9    long total = 0;
10    for (int i = 0; i < sorted.length; i++) {
11        int a = find(parent, sorted[i][0]), b = find(parent, sorted[i][1]);
12        if (a == b) continue;
13        parent[a] = b; inTree[i] = true; total += sorted[i][2];
14        tree[sorted[i][0]].add(new int[]{sorted[i][1], sorted[i][2]});
15        tree[sorted[i][1]].add(new int[]{sorted[i][0], sorted[i][2]});
16    }
17    long best = Long.MAX_VALUE;
18    for (int i = 0; i < sorted.length; i++) {
19        if (inTree[i]) continue;
20        int heaviest = maxOnPath(tree, sorted[i][0], sorted[i][1], -1);   // the swap removes the heaviest tree edge on the cycle
21        best = Math.min(best, total - heaviest + sorted[i][2]);
22    }
23    return best;
24}
25static List<List<Integer>> criticalEdges(int n, int[][] edges) {   // {critical, pseudo-critical} edge indexes
26    long base = mst(n, edges, -1, -1);
27    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
28    for (int i = 0; i < edges.length; i++) {
29        if (mst(n, edges, i, -1) > base) critical.add(i);          // without it the tree is heavier or breaks
30        else if (mst(n, edges, -1, i) == base) pseudo.add(i);      // forced in, still minimum
31    }
32    return List.of(critical, pseudo);
33}

Live state

0 edges examined

0..1

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	S=0..1	A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.
2	L1	crossing=3	3 edges cross the cut: 0-2:3, 1-2:1, 1-3:2.
3	L1	return=1-2:1 tree contains it=yes	The cut property: the lightest crossing edge, 1-2:1, belongs to some minimum spanning tree. Reason: any tree must cross the cut somewhere; swapping a heavier crossing edge for this one keeps it a tree and cannot raise the weight. Kruskal's tree contains it.

36.06.2

Cut proof

**Cut argument.** A spanning tree T is minimum if and only if every tree edge is a lightest edge crossing the cut it defines: deleting a tree edge splits T into two parts, and no edge of the graph joining the two parts may be lighter. If a lighter one existed, swapping it in would improve the tree.

Both conditions say the same thing from two sides: cycles ask about non-tree edges, cuts ask about tree edges. The function below tests every tree edge's cut.

Java

1static boolean isMinimumByCuts(int n, int[][] edges, int[] tree) {   // each tree edge must be a lightest edge across its own cut
2    if (tree.length != n - 1) return false;
3    int[] check = new int[n];
4    for (int i = 0; i < n; i++) check[i] = i;
5    boolean[] seen = new boolean[edges.length];
6    for (int k : tree) {
7        if (seen[k]) return false;
8        seen[k] = true;
9        int a = find(check, edges[k][0]), b = find(check, edges[k][1]);
10        if (a == b) return false;
11        check[a] = b;
12    }
13    for (int skip : tree) {
14        int[] parent = new int[n];
15        for (int i = 0; i < n; i++) parent[i] = i;
16        for (int k : tree) if (k != skip) parent[find(parent, edges[k][0])] = find(parent, edges[k][1]);
17        int side = find(parent, edges[skip][0]);                      // the component of one end after removing the edge
18        for (int k = 0; k < edges.length; k++) {
19            boolean x = find(parent, edges[k][0]) == side, y = find(parent, edges[k][1]) == side;
20            if (x != y && edges[k][2] < edges[skip][2]) return false;   // a lighter edge crosses this cut
21        }
22    }
23    return true;
24}
25static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

MST properties and variations: cut, cycle, second best, critical edges

Interactive · edit the input

undirected graph · 5 vertices · 7 edges

Being examinedIn the minimum spanning treeSide S of the cutHeaviest edge on the path (the swap)Not in the tree

side S

Setup

A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.

Step 1 / 3

Java

1static long secondBestMst(int n, int[][] edges) {   // connected graph; Long.MAX_VALUE when no other spanning tree exists
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    boolean[] inTree = new boolean[sorted.length];
7    List<int[]>[] tree = new List[n];
8    for (int i = 0; i < n; i++) tree[i] = new ArrayList<>();
9    long total = 0;
10    for (int i = 0; i < sorted.length; i++) {
11        int a = find(parent, sorted[i][0]), b = find(parent, sorted[i][1]);
12        if (a == b) continue;
13        parent[a] = b; inTree[i] = true; total += sorted[i][2];
14        tree[sorted[i][0]].add(new int[]{sorted[i][1], sorted[i][2]});
15        tree[sorted[i][1]].add(new int[]{sorted[i][0], sorted[i][2]});
16    }
17    long best = Long.MAX_VALUE;
18    for (int i = 0; i < sorted.length; i++) {
19        if (inTree[i]) continue;
20        int heaviest = maxOnPath(tree, sorted[i][0], sorted[i][1], -1);   // the swap removes the heaviest tree edge on the cycle
21        best = Math.min(best, total - heaviest + sorted[i][2]);
22    }
23    return best;
24}
25static List<List<Integer>> criticalEdges(int n, int[][] edges) {   // {critical, pseudo-critical} edge indexes
26    long base = mst(n, edges, -1, -1);
27    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
28    for (int i = 0; i < edges.length; i++) {
29        if (mst(n, edges, i, -1) > base) critical.add(i);          // without it the tree is heavier or breaks
30        else if (mst(n, edges, -1, i) == base) pseudo.add(i);      // forced in, still minimum
31    }
32    return List.of(critical, pseudo);
33}

Live state

0 edges examined

0..1

No condition evaluated on this step

Execution trace (dry run table)Show 3 steps

Step	Line	State	What happens
1	L1	S=0..1	A cut splits the vertices into S = {0..1} and the rest. The edges with one end on each side cross the cut.
2	L1	crossing=3	3 edges cross the cut: 0-2:3, 1-2:1, 1-3:2.
3	L1	return=1-2:1 tree contains it=yes	The cut property: the lightest crossing edge, 1-2:1, belongs to some minimum spanning tree. Reason: any tree must cross the cut somewhere; swapping a heavier crossing edge for this one keeps it a tree and cannot raise the weight. Kruskal's tree contains it.

36.06.3

Greedy choice

Kruskal's invariant: the edges accepted so far are part of some MST. When the next edge e joins two components, take the cut that separates one of them from everything else. No accepted edge crosses it, and every edge lighter than e was already processed and is either accepted (inside a component) or rejected (inside a component), so e is a lightest crossing edge. By the cut property it can be added: the invariant holds again.

Prim's step is the same, with the cut between the current tree and the rest. The function below checks this safety claim on a concrete graph: for every accepted edge, no edge leaving that component is lighter.

Java

1static boolean everyStepIsSafe(int n, int[][] edges) {              // each Kruskal edge is a lightest edge leaving the component it grows
2    Integer[] order = new Integer[edges.length];
3    for (int i = 0; i < order.length; i++) order[i] = i;
4    Arrays.sort(order, Comparator.comparingInt(i -> edges[i][2]));
5    int[] parent = new int[n];
6    for (int i = 0; i < n; i++) parent[i] = i;
7    for (int k : order) {
8        int a = find(parent, edges[k][0]), b = find(parent, edges[k][1]);
9        if (a == b) continue;
10        for (int j = 0; j < edges.length; j++) {                    // the cut: a's component against everything else
11            boolean x = find(parent, edges[j][0]) == a, y = find(parent, edges[j][1]) == a;
12            if (x != y && edges[j][2] < edges[k][2]) return false;
13        }
14        parent[a] = b;
15    }
16    return true;
17}
18static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }

Minimum spanning tree: Kruskal and Prim (lazy and eager)

Interactive · edit the input

undirected graph · 6 vertices · 8 edges

Edge / vertex being consideredIn the treeRejected (would close a cycle)In the heap or frontier

edges, lightest first

1-2:1

1-3:2

0-2:3

0-1:4

2-3:4

2-4:5

4-5:6

3-4:7

component leader of v

Setup

Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.

Step 1 / 10

Java

1static long kruskal(int n, int[][] edges) {          // edges {u, v, w}; total weight of the minimum spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, Comparator.comparingInt(e -> e[2]));   // lightest first
4    int[] parent = new int[n];
5    for (int i = 0; i < n; i++) parent[i] = i;
6    long total = 0;
7    for (int[] e : sorted) {
8        int a = find(parent, e[0]), b = find(parent, e[1]);
9        if (a == b) continue;                           // already connected: this edge would close a cycle
10        parent[a] = b;
11        total += e[2];
12    }
13    return total;
14}
15static int find(int[] p, int x) { while (p[x] != x) { p[x] = p[p[x]]; x = p[x]; } return x; }
16static long primLazy(int n, List<int[]>[] adj, int s) {   // adj[u] = {v, w}; weight of the tree of s's component
17    boolean[] in = new boolean[n];
18    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);   // {vertex, weight of the edge that reaches it}
19    pq.add(new int[]{s, 0});
20    long total = 0;
21    while (!pq.isEmpty()) {
22        int[] top = pq.poll();
23        if (in[top[0]]) continue;                       // outdated: already in the tree
24        in[top[0]] = true;
25        total += top[1];
26        for (int[] e : adj[top[0]]) if (!in[e[0]]) pq.add(new int[]{e[0], e[1]});
27    }
28    return total;
29}
30static long primEager(int n, List<int[]>[] adj, int s) {   // key[v] = cheapest edge from the tree to v
31    long INF = Long.MAX_VALUE / 2;
32    long[] key = new long[n];
33    Arrays.fill(key, INF);
34    key[s] = 0;
35    boolean[] in = new boolean[n];
36    long total = 0;
37    for (int step = 0; step < n; step++) {
38        int u = -1;
39        for (int v = 0; v < n; v++) if (!in[v] && key[v] < INF && (u == -1 || key[v] < key[u])) u = v;
40        if (u == -1) break;                             // the rest is unreachable
41        in[u] = true;
42        total += key[u];
43        for (int[] e : adj[u]) if (!in[e[0]] && e[1] < key[e[0]]) key[e[0]] = e[1];   // decrease key
44    }
45    return total;
46}

Live state

0 edges examined0 edges rejected

edges

No condition evaluated on this step

Execution trace (dry run table)Show 10 steps

Step	Line	State	What happens
1	L3	n=6 edges=8	Sort the edges by weight (ties keep input order). Every vertex starts as its own component; an edge is taken when it joins two different components.
2	L11	edge=1-2:1 total=1	1-2:1 joins two different components: add it to the tree. Total weight 1.
3	L11	edge=1-3:2 total=3	1-3:2 joins two different components: add it to the tree. Total weight 3.
4	L11	edge=0-2:3 total=6	0-2:3 joins two different components: add it to the tree. Total weight 6.
5	L9	edge=0-1:4	0-1:4: 0 and 1 are already connected through the tree, so this edge would close a cycle. Reject it.
6	L9	edge=2-3:4	2-3:4: 2 and 3 are already connected through the tree, so this edge would close a cycle. Reject it.
7	L11	edge=2-4:5 total=11	2-4:5 joins two different components: add it to the tree. Total weight 11.
8	L11	edge=4-5:6 total=17	4-5:6 joins two different components: add it to the tree. Total weight 17.
9	L9	edge=3-4:7	3-4:7: 3 and 4 are already connected through the tree, so this edge would close a cycle. Reject it.
10	L13	return=17 components=1	The tree has 5 edges and total weight 17 (the smallest possible).

36.06.4

Complexity comparison

Kruskal costs O(m log m) for the sort plus near-constant union-find work, and it needs an edge list. Prim with a binary heap costs O((n + m) log n) and needs an adjacency list. Prim with an array costs O(n²) and needs no heap. In theory O(m log n) and O(m log m) are the same, since log m <= 2 log n; in practice the constants differ.

As a rule: sparse graph or edges already sorted, Kruskal; dense graph, array Prim; in between, heap Prim. The helper below turns that rule into rough operation counts, a guide rather than a benchmark.

Algorithm	Time	Input form	Best for
Kruskal	O(m log m)	edge list	sparse graphs, offline queries, edges sorted already
Prim with a binary heap	O((n + m) log n)	adjacency list	medium density
Prim with an array	O(n²)	matrix or list	dense graphs
Borůvka	O(m log n)	edge list	parallel and distributed settings

Java

1static String suggestMst(int n, int m) {                           // compares rough operation counts
2    double logM = Math.log(Math.max(m, 2)) / Math.log(2), logN = Math.log(Math.max(n, 2)) / Math.log(2);
3    double kruskal = m * logM;
4    double primHeap = (m + n) * logN;
5    double primDense = (double) n * n;
6    if (primDense <= kruskal && primDense <= primHeap) return "Prim, O(n^2) array version";
7    return kruskal <= primHeap ? "Kruskal" : "Prim with a heap";
8}

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Min Cost to Connect All Points
Connecting Cities With Minimum Cost

Advanced

Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
Checking Existence of Edge Length Limited Paths

Key takeaways

A spanning tree is minimum iff no non-tree edge is lighter than an edge on its tree path (cycle condition).
Equivalently, every tree edge is a lightest edge across the cut it defines (cut condition).
Each Kruskal and Prim step takes a lightest edge across a cut that respects the tree so far: always safe.
Kruskal for sparse graphs, array Prim for dense ones, heap Prim in between.