DOI link for Spanning Trees
Spanning Trees book
This chapter demonstrates that several classical algorithms, including depth-first and breadth-first searches, Prim's minimum-spanning-tree method, and Dijkstra's shortest-path method, are special cases or extensions of spanning tree strategy. Spanning trees also provide a foundation for a systematic analysis of the cycle structure of a graph. Depth-first search and breadth-first search are integral parts of numerous algorithms used in computer science, operations research, and other engineering disciplines. Tree-growing for digraphs looks the same as for undirected graphs: in each iteration, a frontier arc is selected and added to the growing tree. The forest-growing scheme is simply the repeated application of Tree-Growing. The Steiner-tree problem often arises in network-design and wiring-layout problems. The chapter establishes a number of properties that highlight the relationship and a certain duality between the edge-cuts and cycles of a graph. One approach trying to solve the maximum-weight problem associated with a hereditary subset system is the simple algorithm known as the greedy algorithm.