Card 09/ 09
Recap: Minimum Spanning Trees
The lightest edge across a cut is safe; Kruskal's sorts edges, Prim's grows a tree, and neither gives shortest paths.
A minimum spanning tree connects every vertex of an undirected weighted graph for the least total weight, and the topic taught one rule that makes it safe to build greedily and two algorithms that apply the rule. The table below lists each idea with the card that taught it.
| The idea | Where |
|---|---|
| Spanning tree, cut, and the cut property, proved by an exchange | Minimum Spanning Trees and the Cut Property |
| Take edges lightest first, skip any whose ends share a tree, stop at V − 1 | Trace Kruskal's Algorithm With Union-Find |
| Union by size and path halving make each check almost free | Kruskal's Algorithm in Python, Java and TypeScript |
| Grow one tree by the lightest edge leaving it | Trace Prim's Algorithm Growing One Tree |
| A heap with lazy deletion, or a scan of best edges in O(V²) | Prim's Algorithm in Python, Java and TypeScript |
| Kruskal's for edge lists and sparse graphs, Prim's for dense ones | Kruskal vs Prim |
| A minimum spanning tree minimises the total, not each route | Reading Shortest Paths From a Minimum Spanning Tree |
| Trace Kruskal's algorithm on a new graph and justify an edge with a cut | Practice: Laying Fibre Between Village Halls |
Every step of both algorithms is the same move: find a cut that no chosen edge crosses, and add the lightest edge that does. Kruskal's algorithm looks at the edges in order of weight and lets union-find say which cut each one is lightest across; Prim's algorithm always uses the cut around its one growing tree. Both are correct for that reason, and both find the same tree when no two weights are equal.
What neither does is route. The tree minimises the sum of its edges, so the path it holds between two vertices can be longer than the shortest one, as A to F was, 17 against 15. A question about getting from one place to another belongs to Dijkstra's algorithm.
Kruskal's algorithm used union-find to tell whether two vertices were already connected. Graph Connectivity, the next topic, asks connection questions of a whole graph: which groups of vertices in a directed graph can all reach one another, and which single vertex or edge would split a network in two if it failed.
← → move through sections and cards