Minimum Spanning Tree: Kruskal's Algorithm

Given a connected, undirected, weighted graph G = (V, E), a spanning tree is a subgraph that:

1. Includes every vertex of G,
2. Is connected, and
3. Contains no cycles (so it has exactly V - 1 edges).

A minimum spanning tree (MST) is a spanning tree whose total edge weight is minimum among all spanning trees of G.

Classic motivating example: "design the cheapest road network that connects all the towns." Other applications include clustering (single-linkage), network design (electricity, fiber, water), approximate TSP, and image segmentation.

A graph may have multiple MSTs if some edges share weights, but every MST has the same total weight.

Kruskal's strategy is the textbook greedy:

1. Sort all edges by weight, smallest first.
2. Initialize an empty MST T and place every vertex in its own set.
3. Scan edges in order. For each edge (u, v, w):
   • If u and v are in different components, add the edge to T and merge the components.
   • If they are in the same component, skip the edge — adding it would create a cycle.
4. Stop after adding V - 1 edges.

Why it works (cut property, informal): at any moment, the cheapest edge that crosses between two components must belong to some MST — if a candidate MST didn't contain it, we could swap it in and lower (or match) the total weight.

The magic is how cheaply we test "different components?" — the disjoint-set data structure answers in near-O(1) amortized time.

Run Kruskal on this 6-vertex weighted graph (vertices A..F renamed 1..6). Step forward and backward with the ← / → arrow keys or the buttons below.

What to watch:

• Node colors show DSU components — every vertex starts as its own color, and accepting an edge merges two colors into one. The small →r label under each vertex is its current DSU root.
• The sorted edge list is scanned left to right: the dashed amber edge is under consideration, green edges joined the MST, red struck-through edges were rejected because both endpoints already share a root — adding them would close a cycle.
• The running MST cost accumulates only the accepted weights.

After 5 accepted edges (= V − 1) the tree is complete with total cost 33 — every later edge can only be rejected.

Cut property (informal): Let S ⊂ V be any non-empty proper subset, and let e be the cheapest edge crossing between S and V \ S. Then some MST contains e.

At the moment Kruskal considers edge e = (u, v) and finds u, v in different components, consider the cut that separates u's component from the rest. Every edge crossing that cut has weight at least w(e) — otherwise we would have already added a cheaper one and merged the components. So e is a cheapest crossing edge for some cut, and by the cut property e belongs to some MST. Adding it keeps our partial selection a subset of an MST.

Cycle property (informal): the heaviest edge on any cycle is unnecessary. Kruskal naturally enforces this: when scanning by increasing weight, an edge closing a cycle is the heaviest on that cycle (every earlier edge of the cycle has already been processed), and so it can be safely skipped.

Together, these two properties say Kruskal never adds a bad edge and never misses a needed one.

Kruskal is two lines of idea — sort, then scan with DSU cycle checks — and the code reflects that. The unite call doubles as the cycle test: it returns false exactly when both endpoints already share a root. The C++ tab is a complete program on the visualization's graph; it prints the MST edges and total weight 33.

Three components contribute to the running time:

• Sorting all E edges: O(E log E). Since E ≤ V², this is the same as O(E log V).
• E calls to DSU Find + Union: O(E · α(V)), essentially O(E).
• Bookkeeping (constructing the result): O(V).

Total time: O(E log E) = O(E log V), dominated by the sort.

Space: O(V + E) — for the edge list and the DSU.

Kruskal is edge-centric and works very well for sparse graphs (graphs that can be stored conveniently as an edge list). For very dense graphs, Prim's algorithm with a binary heap or Fibonacci heap can be faster in practice.