Minimum Spanning Tree
Interactive visualizations for Chapter 9 of the Ricerca Operativa notes
The Undirected Running Graph
We work with an undirected graph of 7 nodes and 11 edges throughout this chapter.
- Nodes: s, a, b, c, d, e, t
- Edges (with weights): s–a(4), s–b(2), a–c(5), a–d(1), a–b(8), b–d(3), c–e(3), c–d(2), d–e(6), d–t(9), e–t(1)
Edges sorted by weight: a–d(1), e–t(1), s–b(2), c–d(2), b–d(3), c–e(3), s–a(4), a–c(5), d–e(6), a–b(8), d–t(9).
Kruskal’s Algorithm
Kruskal’s algorithm builds the MST by greedily adding the cheapest edge that does not create a cycle, processing edges in non-decreasing order of weight.
We use a Union-Find (disjoint-set) data structure to detect cycles efficiently.
| Step | Edge | Weight | Action | Components after |
|---|---|---|---|---|
| 1 | a–d | 1 | Accept | {s}, {a,d}, {b}, {c}, {e}, {t} |
| 2 | e–t | 1 | Accept | {s}, {a,d}, {b}, {c}, {e,t} |
| 3 | s–b | 2 | Accept | {s,b}, {a,d}, {c}, {e,t} |
| 4 | c–d | 2 | Accept | {s,b}, {a,c,d}, {e,t} |
| 5 | b–d | 3 | Accept | {s,a,b,c,d}, {e,t} |
| 6 | c–e | 3 | Accept | {s,a,b,c,d,e,t} — MST complete! |
| 7 | s–a | 4 | Reject (cycle) | — |
| 8 | a–c | 5 | Reject (cycle) | — |
| 9 | d–e | 6 | Reject (cycle) | — |
| 10 | a–b | 8 | Reject (cycle) | — |
| 11 | d–t | 9 | Reject (cycle) | — |
MST edges: a–d(1), e–t(1), s–b(2), c–d(2), b–d(3), c–e(3) — Total weight = 12
Kruskal’s Step-by-Step Table
Prim’s Algorithm from s
Prim’s algorithm grows the MST by always extending the current tree with the minimum-weight edge that connects a tree node to a non-tree node.
Starting from node s:
| Step | Tree T | New frontier edges | Chosen edge | Reason |
|---|---|---|---|---|
| 0 | {s} | s–a(4), s–b(2) | s–b(2) | minimum crossing edge |
| 1 | {s,b} | + b–a(8), b–d(3) | b–d(3) | minimum: b–d(3) |
| 2 | {s,b,d} | + d–a(1), d–c(2), d–e(6), d–t(9) | d–a(1) | minimum: d–a(1) |
| 3 | {s,b,d,a} | + a–c(5) | d–c(2) | minimum: d–c(2) |
| 4 | {s,b,d,a,c} | + c–e(3) | c–e(3) | minimum: c–e(3) |
| 5 | {s,b,d,a,c,e} | + e–t(1) | e–t(1) | minimum: e–t(1) |
MST edges: s–b(2), b–d(3), d–a(1), d–c(2), c–e(3), e–t(1) — Total weight = 12
Prim’s vs Kruskal’s Comparison
Both algorithms find the same MST (when edge weights are distinct the MST is unique — here there are ties but both algorithms converge to the same edge set).
- Kruskal: global view, sorts all edges up front, uses Union-Find to skip cycles.
- Prim: local view, grows a single tree, uses a priority queue over frontier edges.
MST Properties
Cut Property
The cut property is the theoretical foundation for both Kruskal and Prim:
For any cut (S, V\S) of the graph, the minimum-weight edge crossing the cut belongs to the MST.