A minimum spanning tree (MST) is the cheapest way to wire up a connected, weighted graph: pick a subset of edges that touches every vertex, contains no cycle, and has the smallest possible total weight. With V vertices that subset always has exactly V - 1 edges. Kruskal's algorithm finds it with a simple greedy rule plus one clever helper.
The core idea. Sort every edge by weight, then walk them cheapest first. Add an edge if it joins
two different groups of vertices; skip it if both ends are already connected (adding it would form a
cycle). Stop once you have V - 1 edges. A Union-Find (DSU) answers "same group?" almost instantly.
Intuition
Imagine you are laying fiber to connect five towns, and each possible cable has a cost. You want every town reachable while spending the least money. Greedily, you would lay the cheapest cable first, then the next cheapest, and so on — but you would never lay a cable between two towns that are already connected through other cables, because that money buys you nothing new (it just makes a loop). Keep going until every town is on the network. That is exactly Kruskal.
The only tricky part is checking "are these two towns already connected?" fast. That is the job of Union-Find: each town starts in its own group, union merges two groups when you lay a cable, and find tells you which group a town is in. Two towns are connected exactly when find(a) == find(b).
Walk through it
Step through the animation on the right. The edge weights are sorted into the list at the top, and the algorithm processes them in that order: AB(1), BC(2), AC(3), CD(4), DE(5)...
Watch what happens at each one. A-B, B-C, C-D, and D-E each connect a new vertex into the growing tree, so they turn green and the running MST weight ticks up. But A-C is different: by the time we reach it, A and C are already linked through B, so the DSU reports them in the same component and the edge flashes red and is skipped — adding it would make the cycle A-B-C-A. After four green edges we have V - 1 = 4, every vertex is connected, and we stop. The total weight is 1 + 2 + 4 + 5 = 12.
The code, line by line
def kruskal(n, edges):
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
mst, total = [], 0
for w, u, v in sorted(edges):
if find(u) != find(v):
parent[find(u)] = find(v)
mst.append((u, v)); total += w
# else: same set -> skip (cycle)
return mst, totalparent = list(range(n))sets up the DSU: every vertex is its own parent, i.e. its own component.find(x)walks parent pointers to the root ofx's component. Theparent[x] = parent[parent[x]]line is path compression — it flattens the tree as it goes, which keepsfindnear O(1) amortized.sorted(edges)processes edges cheapest first — each tuple is(weight, u, v), so sorting by the tuple sorts by weight.- Line 10,
find(u) != find(v), is the cycle check: different roots means different components, so this edge is safe to add. - Line 11 is the
union— point one root at the other to merge the two components. Line 12 records the edge and adds its weight.
Complexity
| Case | Time | Notes |
|---|---|---|
| Sort the edges | O(E log E) (moderate) | the dominant cost |
| Union-Find ops | O(E α(V)) (moderate) | α is the near-constant inverse Ackermann |
| Overall | O(E log E) (moderate) | = O(E log V), since E < V² |
O(V) (moderate)The runtime is dominated by the sort. Once the edges are ordered, each of the E edges costs only a couple of near-constant DSU operations. The space is O(V) for the parent array.
When to use / pitfalls
Two greedy algorithms find an MST. Kruskal sorts all edges and joins components globally with a DSU — great when edges are few or already sorted. Prim instead grows one tree from a start vertex, repeatedly pulling the cheapest edge that leaves the tree using a min-heap — great on dense graphs. Both are greedy and both give the same minimum total weight; mention the trade-off and the data structure each leans on (DSU vs. heap) and you have answered the question well.
The MST is only defined for a connected graph — if the graph has separate pieces, Kruskal returns a
minimum spanning forest (one tree per piece) and never reaches V - 1 edges. Also note the MST edge
set may not be unique when weights tie, but the total weight always is.
Practice
Edges sorted by weight are AB(1), BC(2), AC(3), CD(4), DE(5). After AB and BC are added, what happens when Kruskal reaches AC(3)?
1. How many edges does an MST of a connected graph with V vertices have?
2. What does Kruskal do when an edge connects two vertices already in the same component?
3. What is the role of Union-Find (DSU) in Kruskal?
4. How does Prim differ from Kruskal?