Lesson 27.1 · Minimum Spanning Trees

Kruskal's Algorithm and the Cut Property

Sort edges by weight and add each one that joins two different components. The cut property guarantees each added edge belongs to some MST.

14 min

Think of it like this

Building roads between villages on a budget: you always build the cheapest remaining road, unless the two villages are already connected some other way, in which case that road would be wasted money.

1.Why greedy works

Cut property: split the nodes into any two groups. The cheapest edge crossing between them is in some MST. (If an MST didn't use it, adding it creates a cycle that crosses the split twice; removing the other crossing edge gives a tree that's no more expensive.)

Kruskal relies on this: when it adds the cheapest edge between two components, that edge is the cheapest crossing the cut around one of them. Union-find tells whether the endpoints are already connected. Cost: O(E log E) for sorting.

Main.java

import java.util.*;

public class Main {
    static int[] parent;
    static int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{0, 1, 1}, {1, 2, 4}, {0, 2, 3}, {2, 3, 2}, {1, 3, 5}};
        Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int total = 0, used = 0;
        for (int[] e : edges) {
            int a = find(e[0]), b = find(e[1]);
            if (a == b) continue;                    // would make a cycle
            parent[a] = b;
            total += e[2];
            used++;
            System.out.println("take " + e[0] + "-" + e[1] + " (" + e[2] + ")");
            if (used == n - 1) break;
        }
        System.out.println("MST weight = " + total);
    }
}

Output

take 0-1 (1)
take 2-3 (2)
take 0-2 (3)
MST weight = 6

▶ Dry run: Kruskal on 4 nodesedges: 0-1 (1), 2-3 (2), 0-2 (3), 1-2 (4), 1-3 (5)

Step 1/5Sort edges by weight: 1, 2, 3, 4, 5.

Remember

Sort edges; skip those inside one component.
Stop at n − 1 edges.
Fewer than n − 1 edges taken ⇒ graph is disconnected.

Common mistakes

Running on a directed graph (MST is for undirected graphs).
Forgetting the disconnected case.

Words used in this lesson

Spanning tree: A subset of edges that connects every node without cycles: exactly n − 1 edges.
Cut: A split of the nodes into two groups; crossing edges have one end in each.

Command Palette

Kruskal's Algorithm and the Cut Property

1.Why greedy works