Generic algorithm, safe edge algorithm, Kruskal’s algorithm, Prim’s algorithm, shortest path, dense paths.
Understand when, why, and how to use minimum spanning trees.
Including the generic algorithm and the safe edge theorem
Screencast Suthers 17 min
Kruskal’s minimum spanning tree algorithm, with example and analysis.
Screencast Suthers 13 min
Prim’s minimum spanning tree algorithm, with example and analysis.
Screencast Suthers 15 min
Growing a minimum spanning tree, the algorithms of Kruskal and Prim.
Textbook 19 pages
Minimum spanning trees, shortest path, dense paths, geometric problems
Textbook 14 pages
Minimum spanning trees, the generic algorithm, Kruskal’s and Prim’s algorithms
Notes