1. Review Sites
  2. Home
  3. Modules
  4. Minimum spanning tree

Module: Minimum spanning tree

Generic algorithm, safe edge algorithm, Kruskal’s algorithm, Prim’s algorithm, shortest path, dense paths.

Learning Outcomes

Characterize behavior of minimum spanning tree data structures, including:

Readings

Introduction to minimum spanning trees

Including the generic algorithm and the safe edge theorem

Screencast Suthers 17 min

Kruskal's algorithm

Kruskal’s minimum spanning tree algorithm, with example and analysis.

Screencast Suthers 13 min

Prim's algorithm

Prim’s minimum spanning tree algorithm, with example and analysis.

Screencast Suthers 15 min

CLRS 23 - Minimum spanning trees

Growing a minimum spanning tree, the algorithms of Kruskal and Prim.

Textbook 19 pages

Sedgewick 31 - Weighted graphs

Minimum spanning trees, shortest path, dense paths, geometric problems

Textbook 14 pages

Notes on minimum spanning trees

Minimum spanning trees, the generic algorithm, Kruskal’s and Prim’s algorithms

Notes

Experiential Learning

More minimum spanning trees

Minimum spanning trees and Kruskal’s algorithm

Homework