DSA Kruskal's Algorithm
A minimum spanning tree is the cheapest set of edges that connects every vertex with no cycles. Kruskal's algorithm builds it by taking the cheapest edges that never close a cycle.
Cheapest first
Sorting by weight lines the edges up for judgement. Each edge is then considered exactly once, in this order.
edges = [(2, 3, 9), (0, 1, 2), (1, 2, 5), (0, 2, 4)]
edges.sort(key=lambda e: e[2])
for u, v, w in edges:
print(u, "-", v, "weight", w)
Union-find remembers the groups
After two unions, nodes 0 and 2 report the same root. An edge between them would close a cycle and must be refused.
parent = list(range(4))
def find(x):
while parent[x] != x:
x = parent[x]
return x
for u, v in [(0, 1), (1, 2)]:
parent[find(u)] = find(v)
print("union", u, v, "roots:", [find(i) for i in range(4)])
print("0 and 2 already joined:", find(0) == find(2))
print("edge 0 - 2 would close a cycle: refused")
Take or refuse
The two cheap edges of this triangle join all three nodes. The third edge is refused, and the total stays 3.
edges = [(0, 1, 1), (1, 2, 2), (0, 2, 3)]
parent = list(range(3))
def find(x):
while parent[x] != x:
x = parent[x]
return x
total = 0
for u, v, w in sorted(edges, key=lambda e: e[2]):
if find(u) == find(v):
print(u, "-", v, "refused")
else:
parent[find(u)] = find(v)
total += w
print(u, "-", v, "taken, total", total)
Example
edges = [(0, 1, 2), (1, 2, 3), (2, 3, 4), (1, 4, 5),
(0, 3, 6), (2, 4, 7), (1, 3, 8), (3, 4, 9)]
parent = list(range(5))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
total = 0
taken = 0
refused = 0
for u, v, w in sorted(edges, key=lambda e: e[2]):
if find(u) == find(v):
refused += 1
print(u, "-", v, "weight", w, "refused: cycle")
else:
parent[find(u)] = find(v)
total += w
taken += 1
print(u, "-", v, "weight", w, "taken, total", total)
print("MST cost:", total, "edges taken:", taken, "refused:", refused)
Key points
- Edges enter consideration one at a time in rising weight order.
- Ties in weight keep their input order, because the sort is stable.
- Union-find is a structure that joins groups and reports the group of any vertex.
- An edge whose ends already share a group would close a cycle.
- Such an edge is refused, however cheap it is.
- The tree is complete after exactly n minus 1 accepted edges.
In this example, four edges are taken and the tree completes at a total cost of 14. The four heavier edges are each refused, because their ends already share one tree by then. The refusals are printed in the trace, not hidden.
Note
the refused edges still earn their place, because each refusal certifies a cycle.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
An edge joins two vertices that already share one tree. What does Kruskal's algorithm do?