Spanning Tree
- Describe what spanning tree.
A spanning tree of a connected undirected graph is a subgraph of it (every edge in the tree belongs to ) that spans (it includes every vertex of ).
Consider this graph:
Every tree below is a spanning tree of the graph above.
As can be seen above, a graph may have several spanning trees.
A spanning tree can be built by doing a BFS/DFS of the graph.
Recall the demo for BFS/DFS from prior chapters:
The spanning trees consist (only) of the thick edges.
Resources
- Wikipedia's entry on Spanning Tree.
- Computerphile's YouTube video on Software Defined Networking — an example of an application of spanning trees.