Editing Spanning tree (section)

==Applications==
Several [[pathfinding]] algorithms, including [[Dijkstra's algorithm]] and the [[A* search algorithm]], internally build a spanning tree as an intermediate step in solving the problem.

In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the [[minimum spanning tree]].<ref>{{citation|first1=R. L.|last1=Graham|first2=Pavol|last2=Hell|url=http://www.math.ucsd.edu/~ronspubs/85_07_minimum_spanning_tree.pdf|title=On the History of the Minimum Spanning Tree Problem|date=1985}}</ref>

The Internet and many other [[telecommunications network]]s have transmission links that connect nodes together in a [[mesh topology]] that includes some loops.
In order to avoid [[bridge loop]]s and [[routing loop]]s, many routing protocols designed for such networks—including the [[Spanning Tree Protocol]], [[Open Shortest Path First]], [[Link-state routing protocol]], [[Augmented tree-based routing]], etc.—require each router to remember a spanning tree.<ref name="https://en.wikipedia.org/w/index.php?title=Spanning_tree&action=edit#">{{citation|last1=Borg |first1=Anita |title=Folklore of Network Protocol Design |url=https://www.youtube.com/watch?v=CcmfS8Ue7G4 |website=YouTube |date=5 September 2016 |publisher=Microsoft Research |access-date=13 May 2022}}</ref>

A special kind of spanning tree, the [[Xuong tree]], is used in [[topological graph theory]] to find [[graph embedding]]s with maximum [[genus (mathematics)|genus]]. A Xuong tree is a spanning tree such that, in the remaining graph, the number of connected components with an odd number of edges is as small as possible. A Xuong tree and an associated maximum-genus embedding can be found in [[polynomial time]].<ref>{{citation
 | last1 = Beineke | first1 = Lowell W. | author1-link = L. W. Beineke
 | last2 = Wilson | first2 = Robin J. | author2-link = Robin Wilson (mathematician)
 | doi = 10.1017/CBO9781139087223
 | isbn = 978-0-521-80230-7
 | mr = 2581536
 | page = 36
 | publisher = Cambridge University Press, Cambridge
 | series = Encyclopedia of Mathematics and its Applications
 | title = Topics in topological graph theory
 | volume = 128
 | year = 2009}}</ref>