November 2024
Intermediate to advanced
416 pages
11h 11m
English
The minimum spanning tree of a weighted, undirected graph is the set of edges with the smallest total weight that connects all the nodes. We can use this concept to model and optimize a variety of real-world problems, from designing power grids to hypothesizing how chipmunks should be constructing their burrows.
This chapter introduces two classical algorithms for constructing minimum spanning trees. Prim’s algorithm is a nodewise agglomerative algorithm that builds a bigger and bigger set of connected nodes. Kruskal’s algorithm constructs a minimum spanning tree from a sorted list of edges by adding one edge at ...