Editing Spanning tree (section)

===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>