Spanning Trees

Math for CS · Axiom Academy

Connecting every vertex with minimum edges A spanning tree keeps all vertices connected while using the fewest possible edges. It is the "skeleton" of the graph. Existence and Finding Spanning Trees Every connected graph has at least one spanning tree. Both BFS and DFS naturally produce one. Run BFS from any vertex. The edges used to discover new vertices form a spanning tree. This tree has the property that BFS-tree paths are shortest paths (in terms of edge count) from the root. Run DFS from any vertex. The edges used to discover new vertices form a spanning tree. DFS trees have useful properties for finding bridges, articulation points, and strongly connected components. Proof: T has a unique path between any two vertices. If edge is not in T , then e plus the unique u - v path in T forms exactly one cycle. One spanning tree: (path from A to D ) Adding non-tree edge creates cycle A-B-C-D-A Adding non-tree edge creates cycle A-B-C-A Removing tree edge splits into and The MST answers: what is the cheapest way to connect all vertices? This has direct applications in network design, clustering, and approximation algorithms. Two classic greedy algorithms find the MST. Both are covered in detail in the next lesson. Sort all edges by weight. Add edges in order, skipping any that would create a cycle. Uses a union-find data structure. Start from any vertex. Repeatedly add the cheapest edge connecting the tree to a non-tree vertex. Uses a priority queue .

This is the written version of the interactive lesson above. See the full Math for CS course.