Breadcrumbs Section. Click here to navigate to respective pages.
Chapter

Chapter
Spanning Trees
DOI link for Spanning Trees
Spanning Trees book
Spanning Trees
DOI link for Spanning Trees
Spanning Trees book
ABSTRACT
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.