Visualizer CodeViz · Algorithms, visualized

Part II · Minimum spanning trees · week 3

Kruskal's MST

Sort the edges and take them in order, skipping any that would create a cycle. The cycle test is union-find, which is why this is barely more than a sort.

Run the animation, step by step → generated live from any input you type — nothing is pre-recorded

Cost and properties

timeO(E log E)
dominated bysorting the edges
cycle testunion-find, ~constant
greedyprovably optimal

Reference: Sedgewick & Wayne, §4.3; Kruskal 1956.

Kruskal's MST in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class KruskalMST:
    # Consider edges in ASCENDING weight order and take each one unless it
    # would create a cycle. Union-find answers 'same tree already?' in
    # near-constant time, so the sort dominates the cost.

    def __init__(self, graph):
        self.mst = []
        self.weight = 0.0
        uf = WeightedQuickUnionUF(graph.V)
        for e in sorted(graph.edges(), key=lambda e: e.weight):
            v, w = e.v, e.w
            if uf.find(v) != uf.find(w):  # different trees: no cycle
                uf.union(v, w)
                self.mst.append(e)
                self.weight += e.weight
            if len(self.mst) == graph.V - 1:
                break                     # V-1 edges is a spanning tree

Why it works

Why greedy works here: the cut property

Cut property: given any cut of the graph, the minimum-weight crossing edge is in the MST. Kruskal is that property applied repeatedly — when it accepts an edge, that edge is the smallest one crossing the cut between the two trees it joins, so it is safe. Greedy algorithms are usually wrong; MST is one of the few problems where a greedy rule is provably optimal, and the cut property is the proof.

The cycle test is the whole engineering problem

“Would this edge create a cycle?” by DFS would cost O(V) per edge. Union-find answers it by comparing roots — essentially constant — so the total cost collapses to the sort: O(E log E). This is the payoff for the first week of Part I; the union-find work makes the MST algorithm nearly free.

Stopping early

A spanning tree of V vertices has exactly V−1 edges, so the loop can stop as soon as it has that many — often long before examining the heavy edges. Watch the counter: on tinyEWG the last few edges (0.93, 0.58, 0.52) are never even considered.

Equal weights and uniqueness

With distinct weights the MST is unique. With ties there may be several MSTs of equal weight, and which one you get depends on the sort's tie-breaking — not on any property of the graph. Try the equal weights preset: the result is a spanning tree chosen by input order alone.

Also note a disconnected graph has no spanning tree; both this and Prim then produce a spanning forest of the component they can reach.

What to try in the animation

Edges are v-w:weight. The default is tinyEWG.txt from the course — its MST weight is 1.81.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

Open Kruskal's MST in the player →

The rest of Minimum spanning trees