Algorithms
The classic spanning tree algorithm, depth-first search (DFS), is due to Robert Tarjan. Another important algorithm is based on breadth-first search (BFS).
Parallel algorithms typically take different approaches than BFS or DFS. Halperin and Zwick designed an optimal randomized parallel algorithm that runs in O(log n) time with high probability on EREW PRAM. The Shiloach-Vishkin algorithm, due to Yossi Shiloach and Uzi Vishkin, is the basis for many parallel implementations. Bader and Cong's algorithm is shown to run fast in practice on a variety of graphs.
The most common distributed algorithm is the Spanning Tree Protocol, used by OSI link layer devices to create a spanning tree using the existing links as the source graph in order to avoid broadcast storms.
Read more about this topic: Spanning Tree