36.04Intermediate / Advanced4 topics17 min3 interactive animations

MST variations

Common variants of the MST problem: the second-best tree, edges that are critical or only pseudo-critical, maximum spanning trees, and updating a tree when an edge is added.

Learning goals

Find the second-best spanning tree by one edge swap
Classify each edge as critical, pseudo-critical or useless
Compute a maximum spanning tree
Update the minimum spanning tree when an edge is added or its weight changes

Prerequisites

Kruskal's algorithmPrim's algorithm

Real questions go beyond one cheapest tree: what is the cheapest backup network? which cables can never be dropped? what happens when a new link appears? Each follows from the structure of the tree.

36.04.1

Second-best MST

The **second-best spanning tree** is the cheapest tree different from the minimum one. It always differs from the MST by a single swap: add a non-tree edge e, which creates a cycle, and remove the heaviest tree edge on that cycle. Try every non-tree edge and keep the smallest result: total - heaviestOnPath + w(e).

If the graph has several MSTs, the second-best has the same weight as the first. If the graph is already a tree, no other spanning tree exists. The *Second-best tree* option shows each swap candidate; each costs a path query, O(n) here.

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;
14        inTree[i] = true;
15        total += sorted[i][2];
16        tree[sorted[i][0]].add(new int[]{sorted[i][1], sorted[i][2]});
17        tree[sorted[i][1]].add(new int[]{sorted[i][0], sorted[i][2]});
18    }
19    long best = Long.MAX_VALUE;
20    for (int i = 0; i < sorted.length; i++) {
21        if (inTree[i]) continue;
22        int heaviest = maxOnPath(tree, sorted[i][0], sorted[i][1], -1);   // the swap removes the heaviest tree edge on the cycle
23        best = Math.min(best, total - heaviest + sorted[i][2]);
24    }
25    return best;
26}
27static int maxOnPath(List<int[]>[] tree, int u, int target, int from) {   // heaviest edge on the tree path, -1 if target is not below u
28    if (u == target) return 0;
29    for (int[] e : tree[u]) {
30        if (e[0] == from) continue;
31        int sub = maxOnPath(tree, e[0], target, u);
32        if (sub >= 0) return Math.max(sub, e[1]);
33    }
34    return -1;
35}
36static 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.04.2

Critical and pseudo-critical edges

An edge is **critical** if it is in every minimum spanning tree: removing it raises the minimum weight (or disconnects the graph). It is **pseudo-critical** if it is in some MST but not all: forcing it into the tree still gives the minimum weight, yet it is not required. The remaining edges are in no MST.

The direct method: compute the MST weight, then for each edge compute the best weight without it and, if that did not change, the best weight with it forced in. That is O(m) runs of Kruskal. The animation prints the verdict for every edge in input order.

Java

1static List<List<Integer>> criticalEdges(int n, int[][] edges) {   // {critical indexes, pseudo-critical indexes}
2    long base = mst(n, edges, -1, -1);
3    List<Integer> critical = new ArrayList<>(), pseudo = new ArrayList<>();
4    for (int i = 0; i < edges.length; i++) {
5        if (mst(n, edges, i, -1) > base) critical.add(i);          // without it the tree is heavier or breaks
6        else if (mst(n, edges, -1, i) == base) pseudo.add(i);      // forced in, still minimum
7    }
8    return List.of(critical, pseudo);
9}
10static long mst(int n, int[][] edges, int skip, int force) {       // Kruskal without edge skip, edge force taken first; Long.MAX_VALUE when disconnected
11    Integer[] order = new Integer[edges.length];
12    for (int i = 0; i < order.length; i++) order[i] = i;
13    Arrays.sort(order, Comparator.comparingInt(i -> edges[i][2]));
14    int[] parent = new int[n];
15    for (int i = 0; i < n; i++) parent[i] = i;
16    long total = 0;
17    int used = 0;
18    if (force >= 0) {
19        parent[find(parent, edges[force][0])] = find(parent, edges[force][1]);
20        total += edges[force][2];
21        used++;
22    }
23    for (int k : order) {
24        if (k == skip || k == force) continue;
25        int a = find(parent, edges[k][0]), b = find(parent, edges[k][1]);
26        if (a == b) continue;
27        parent[a] = b;
28        total += edges[k][2];
29        used++;
30    }
31    return used == n - 1 ? total : Long.MAX_VALUE;
32}
33static 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.04.3

Maximum spanning tree

A **maximum spanning tree** keeps the same structure, but takes the heaviest edges. Sort in descending order and run Kruskal, or negate every weight and run the minimum version. The cut and cycle properties hold with the inequalities reversed.

A common use is to find the most reliable (or widest) connections, for example the network in which the weakest link is as strong as possible. The fourth option of the first animation shows a maximum spanning tree on the Kruskal graph.

Java

1static long maximumSpanningForest(int n, int[][] edges) {          // total weight of the heaviest spanning forest
2    int[][] sorted = edges.clone();
3    Arrays.sort(sorted, (a, b) -> Integer.compare(b[2], a[2]));    // heaviest 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;
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; }

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.04.4

MST under edge changes

If the MST is known and **a new edge** (u, v, w) is added, the new minimum tree is either the old tree or the old tree with one swap: if w is smaller than the heaviest edge on the tree path between u and v, replace that heaviest edge by the new one. This is O(n) instead of rerunning Kruskal.

If a **tree edge gets heavier** or a **non-tree edge gets lighter**, similar one-swap repairs apply (the first needs the lightest non-tree edge across the cut that the removed edge defines, the second the heaviest edge on the new edge's cycle). If a non-tree edge gets heavier or a tree edge lighter, nothing changes.

Java

1static long mstAfterAddingEdge(int n, int[][] tree, int[] extra) {   // tree: the n - 1 edges {u, v, w} of a minimum spanning tree
2    List<int[]>[] adj = new List[n];
3    for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
4    long total = 0;
5    for (int[] e : tree) {
6        adj[e[0]].add(new int[]{e[1], e[2]});
7        adj[e[1]].add(new int[]{e[0], e[2]});
8        total += e[2];
9    }
10    int heaviest = maxOnPath(adj, extra[0], extra[1], -1);
11    return heaviest > extra[2] ? total - heaviest + extra[2] : total;   // swap only when the newcomer is lighter
12}
13static int maxOnPath(List<int[]>[] tree, int u, int target, int from) {
14    if (u == target) return 0;
15    for (int[] e : tree[u]) {
16        if (e[0] == from) continue;
17        int sub = maxOnPath(tree, e[0], target, u);
18        if (sub >= 0) return Math.max(sub, e[1]);
19    }
20    return -1;
21}

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

Min Cost to Connect All Points
Number of Operations to Make Network Connected

Advanced

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

Key takeaways

Second-best tree: try each non-tree edge, remove the heaviest tree edge on its cycle, keep the best.
Critical edges are in every MST; pseudo-critical edges are in some; the rest are in none.
A maximum spanning tree is Kruskal with the order reversed.
Adding an edge to an MST needs only one swap, found from the path maximum.