Kruskal

DSUF-5 and GRDY-5 both met Kruskal’s method in one sentence: take the edges from cheapest to most expensive, and keep each one that does not close a loop. This lesson builds it in full, with its cost and its uses.

Cheapest first, skip loops

1. Sort the edges by cost.
2. Start with no edges: every vertex is a group on its own.
3. For each edge u–v in order: if u and v are in different groups, keep the edge and join the two groups. If they are in the same group, the kept edges already join them, and this edge would close a loop: skip it.
4. Stop when V − 1 edges are kept.

Joseph Kruskal published it in 1956. It is greedy (GRDY-1): each step takes the cheapest edge that is still allowed and never takes it back. Lesson 4 proves it gives a cheapest tree. Step through the figure; each vertex’s tag names its group, and skipped edges are dashed.

Union-find does the checking

“Are u and v in the same group?” and “join their groups” are exactly the two operations of union-find (DSUF). With union by size and path halving, each costs nearly O(1) (DSUF-4).

# find and union are a union-find (DSUF): find(x) names x's group
total = 0
for u, v, w in sorted(edges, key=lambda e: e[2]):   # cheapest first
    if find(u) != find(v):          # different groups: no loop
        union(u, v)
        total += w

That loop is the whole method; SPAN-P2 asks you to write it in full, with the union-find, and to return the lines kept. DSUF-2 explains why linking the smaller group under the larger keeps finds short, and path halving alone already keeps them short in practice. A version without union-find, which relabels every vertex of one group on each join, is correct but can cost O(V²), that is V times V steps: on a chain of edges listed in order, each join relabels the whole growing group. SPAN-P2 has that test. Relabelling only the smaller group is O(V log V), because a vertex that is relabelled always lands in a group at least twice as big.

What it costs

Sorting is O(E log E), which is the same as O(E log V) because E is at most V² (V times V). The union-find work is nearly O(E). So the whole method is O(E log V), and the sort is the slowest part. If the costs are small whole numbers, a counting sort (SORT-6) makes it nearly O(E).

The key in the code above sorts by cost only. Python’s sort is stable (SORT-7), so edges of equal cost stay in list order, and which of several cheapest trees you get depends on that order. operator.itemgetter(2) as the key does the same a little faster, and storing edges as (w, u, v) lets a plain sort() work.

Forests, ties, and clusters

• Not connected. If the graph has several parts, Kruskal’s method gives a cheapest tree for each, a minimum spanning forest, with V − (number of parts) edges. Fewer than V − 1 kept edges means the graph is not connected.
• Ties. When costs repeat, the order among equal edges decides which cheapest tree comes out. All of them cost the same. Lesson 4 shows which edges can appear in some cheapest tree.
• Clusters. Stop Kruskal’s method when k groups are left. The groups are the best split into k clusters in one exact sense: the cheapest edge between two different groups is as expensive as possible. This is single-linkage clustering.
• Matroids. GRDY-5 named the reason greedy works here: sets of edges without a loop form a matroid, and on a matroid “cheapest allowed item first” is always best. Lesson 4 proves it for trees directly.

Now try SPAN-P2, The cheapest network.