Editing Spanning tree (section)

==Algorithms==

===Construction===
A single spanning tree of a graph can be found in [[linear time]] by either [[depth-first search]] or [[breadth-first search]]. Both of these algorithms explore the given graph, starting from an arbitrary vertex ''v'', by looping through the neighbors of the vertices they discover and adding each unexplored neighbor to a data structure to be explored later. They differ in whether this data structure is a  [[Stack (abstract data type)|stack]] (in the case of depth-first search) or a  [[Queue (abstract data type)|queue]] (in the case of breadth-first search). In either case, one can form a spanning tree by connecting each vertex, other than the root vertex ''v'', to the vertex from which it was discovered. This tree is known as a depth-first search tree or a breadth-first search tree according to the graph exploration algorithm used to construct it.<ref>{{citation |title=The Design and Analysis of Algorithms|series=Monographs in Computer Science |first=Dexter |last=Kozen |author-link=Dexter Kozen |publisher=Springer |year=1992 |isbn=978-0-387-97687-7 |page=19 |url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA19}}.</ref> Depth-first search trees are a special case of a class of spanning trees called [[Trémaux tree]]s, named after the 19th-century discoverer of depth-first search.<ref>{{citation
 | last1 = de Fraysseix | first1 = Hubert
 | last2 = Rosenstiehl | first2 = Pierre | author2-link = Pierre Rosenstiehl
 | contribution = A depth-first-search characterization of planarity
 | location = Amsterdam
 | mr = 671906
 | pages = 75–80
 | publisher = North-Holland
 | series = Ann. Discrete Math.
 | title = Graph theory (Cambridge, 1981)
 | volume = 13
 | year = 1982}}.</ref>

Spanning trees are important in parallel and distributed computing, as a way of maintaining communications between a set of processors; see for instance the [[Spanning Tree Protocol]] used by [[Data link layer|OSI link layer]] devices or the Shout (protocol) for distributed computing. However, the depth-first and breadth-first methods for constructing spanning trees on sequential computers are not well suited for parallel and distributed computers.<ref>{{citation
 | last = Reif | first = John H. | author-link = John Reif
 | doi = 10.1016/0020-0190(85)90024-9
 | issue = 5
 | journal = Information Processing Letters
 | mr = 801987
 | pages = 229–234
 | title = Depth-first search is inherently sequential
 | volume = 20
 | year = 1985}}.</ref> Instead, researchers have devised several more specialized algorithms for finding spanning trees in these models of computation.<ref>{{citation
 | last1 = Gallager | first1 = R. G.
 | last2 = Humblet | first2 = P. A.
 | last3 = Spira | first3 = P. M.
 | doi = 10.1145/357195.357200
 | issue = 1
 | journal = ACM Transactions on Programming Languages and Systems
 | pages = 66–77
 | title = A distributed algorithm for minimum-weight spanning trees
 | volume = 5
 | year = 1983| doi-access = free
}}; {{citation
 | last = Gazit | first = Hillel
 | doi = 10.1137/0220066
 | issue = 6
 | journal = SIAM Journal on Computing
 | mr = 1135748
 | pages = 1046–1067
 | title = An optimal randomized parallel algorithm for finding connected components in a graph
 | volume = 20
 | year = 1991}}; {{citation
 | last1 = Bader | first1 = David A.
 | last2 = Cong | first2 = Guojing
 | doi = 10.1016/j.jpdc.2005.03.011
 | issue = 9
 | journal = Journal of Parallel and Distributed Computing
 | pages = 994–1006
 | title = A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
 | url = http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf
 | volume = 65
 | year = 2005
| hdl = 1853/14355
 |url-status=dead |archive-url=https://web.archive.org/web/20150923201604/http://www.cc.gatech.edu/fac/bader/papers/SpanningTree-JPDC2005.pdf |archive-date= Sep 23, 2015 }}.</ref>

===Optimization===
In certain fields of graph theory it is often useful to find a [[minimum spanning tree]] of a [[weighted graph]]. Other optimization problems on spanning trees have also been studied, including the maximum spanning tree, the minimum tree that spans at least k vertices, the [[Minimum degree spanning tree|spanning tree with the fewest edges per vertex]], the [[maximum leaf spanning tree|spanning tree with the largest number of leaves]], the spanning tree with the fewest leaves (closely related to the [[Hamiltonian path problem]]), the [[minimum-diameter spanning tree]], and the minimum dilation spanning tree.<ref name="sts">{{citation |last=Eppstein |first=David |author-link=David Eppstein |contribution=Spanning trees and spanners |title=Handbook of Computational Geometry|editor1-first=J.-R.|editor1-last=Sack|editor1-link=Jörg-Rüdiger Sack|editor2-first=J.|editor2-last=Urrutia|editor2-link=Jorge Urrutia Galicia |publisher=Elsevier |year=1999 |pages=425–461 |contribution-url=http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf |url-status=live |archive-url=https://web.archive.org/web/20230802121548/https://www.ics.uci.edu/~eppstein/pubs/Epp-TR-96-16.pdf |archive-date= Aug 2, 2023 }}.</ref><ref>{{citation |last1=Wu |first1=Bang Ye |last2=Chao |first2=Kun-Mao |title=Spanning Trees and Optimization Problems |year=2004 |publisher=CRC Press |isbn=1-58488-436-3}}.</ref>

Optimal spanning tree problems have also been studied for finite sets of points in a geometric space such as the [[Euclidean plane]]. For such an input, a spanning tree is again a tree that has as its vertices the given points. The quality of the tree is measured in the same way as in a graph, using the Euclidean distance between pairs of points as the weight for each edge. Thus, for instance, a [[Euclidean minimum spanning tree]] is the same as a graph minimum spanning tree in a [[complete graph]] with Euclidean edge weights. However, it is not necessary to construct this graph in order to solve the optimization problem; the Euclidean minimum spanning tree problem, for instance, can be solved more efficiently in ''O''(''n''&nbsp;log&nbsp;''n'') time by constructing the [[Delaunay triangulation]] and then applying a linear time [[planar graph]] minimum spanning tree algorithm to the resulting triangulation.<ref name="sts" />

===Randomization===
A spanning tree chosen [[random]]ly from among all the spanning trees with equal probability is called a [[uniform spanning tree]]. Wilson's algorithm can be used to generate uniform spanning trees in polynomial time by a process of taking a random walk on the given graph and erasing the cycles created by this walk.<ref>{{citation
 | last = Wilson | first = David Bruce
 | contribution = Generating random spanning trees more quickly than the cover time
 | doi = 10.1145/237814.237880
 | mr = 1427525
 | pages = 296–303
 | title = Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996)
 | year = 1996| title-link = Symposium on Theory of Computing
 | isbn = 0-89791-785-5
 }}.</ref>

An alternative model for generating spanning trees randomly but not uniformly is the [[random minimal spanning tree]]. In this model, the edges of the graph are assigned random weights and then the [[minimum spanning tree]] of the weighted graph is constructed.<ref>{{citation
 | last1 = McDiarmid | first1 = Colin
 | last2 = Johnson | first2 = Theodore
 | last3 = Stone | first3 = Harold S.
 | doi = 10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.3.CO;2-Y
 | issue = 1–2
 | journal = Random Structures & Algorithms
 | mr = 1611522
 | pages = 187–204
 | title = On finding a minimum spanning tree in a network with random weights
 | url = http://www.stats.ox.ac.uk/~cstone/mst.pdf
 | volume = 10
 | year = 1997}}.</ref>

===Enumeration===
Because a graph may have exponentially many spanning trees, it is not possible to list them all in [[polynomial time]]. However, algorithms are known for listing all spanning trees in polynomial time per tree.<ref>{{citation
 | last1 = Gabow | first1 = Harold N. | author1-link = Harold N. Gabow
 | last2 = Myers | first2 = Eugene W. | author2-link = Eugene Myers
 | doi = 10.1137/0207024
 | issue = 3
 | journal = [[SIAM Journal on Computing]]
 | mr = 0495152
 | pages = 280–287
 | title = Finding all spanning trees of directed and undirected graphs
 | volume = 7
 | year = 1978}}</ref>