Kruskal Method¶

Definition¶

The Kruskal method constructs a minimum spanning tree by starting with no selected edges and repeatedly choosing a shortest unselected edge that does not create a cycle with the already selected edges. Stop once the selected edges connect all vertices.

Interpretation¶

The Kruskal method builds a minimum spanning tree by always taking the shortest edge that is still allowed. The selected edges may initially form several separate pieces; the method joins those pieces while avoiding unnecessary loops.

A weighted network from A to F with each edge labelled by the order in which Kruskal's method considers it; the accepted edges form a minimum spanning tree of length 13, and the edge AB is skipped.

The labels give the order in which the edges are considered, by increasing length. The first four, $B-C$ $C$ , $A-C$ $C$ , $D-E$ and $E-F$ $F$ , are accepted and form two pieces, $\{A,B,C\}$ and $\{D,E,F\}$ . The fifth edge, $A-B$ $B$ , is skipped because $A$ and $B$ are already joined through $C$ . The sixth, $B-D$ $D$ , joins the two pieces, and with $6-1=5$ edges the tree is complete, of total length 13.

The test "does this edge create a cycle?" is the same as asking whether its two endpoints already lie in the same piece. An edge between two different pieces merges them; an edge inside one piece adds nothing to connectedness and would close a cycle. Once $n-1$ edges are accepted, all vertices lie in one piece, so the remaining edges need not be inspected.

Always taking the cheapest available step is often only a heuristic, without a guarantee of optimality; for spanning trees it is exact, which is why the method always ends with a minimum spanning tree. The Dijkstra-Prim method instead grows a single connected tree from a start vertex. Both reach the same minimum total length, possibly with different trees when there are ties.

Key Results¶

Equivalently, inspect edges in nondecreasing order and reject any that create a cycle.
For $n$ vertices, a completed tree has $n-1$ selected edges.
Equal-length eligible edges may be chosen in any order.

Examples¶

For the figure, the sorted weights are $1,2,2,3,4,5,6,8,10$ . Accept $BC,AC,DE,EF$ , reject $AB$ because it closes $A-B-C-A$ $A$ , then accept $BD$ . These $n-1=5$ edges have total length 13.

If A-B and B-C are already selected, adding A-C would create a cycle and must be rejected.
Week 4 practice 3 has three independent binary tie choices, giving $2^3=8$ minimum trees.

Prerequisites¶

Dijkstra-Prim Method

Sources¶

OR Modelling · Week 4

Aliases: Kruskal's algorithm

Last updated: 20 October 2026 03:02