10 MINIMUM SPANNING TREES
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 ...
Get Graph Algorithms the Fun Way now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
