SpanningTree

A spanning tree of a finite graph is a subgraph that is a tree and includes all the vertices of the original graph. For a connected graph with n vertices, any spanning tree has exactly n−1 edges and is acyclic, while remaining connected. Spanning trees provide a minimal framework that preserves reachability among vertices.

If the original graph is disconnected, it does not have a spanning tree; instead, each connected component has its own spanning tree, and together they form a spanning forest of the graph.

Minimum spanning trees and algorithms. In weighted graphs, a related concept is the minimum spanning tree (MST): among all spanning trees, the one with the smallest total edge weight. Prim's algorithm grows a tree by adding the cheapest edge that connects a new vertex; Kruskal's algorithm processes edges in increasing weight and adds one that connects two components, using a union-find data structure. Both run in near-linear time on typical graphs.

Properties. Spanning trees have several properties: every connected graph has spanning trees; the number of distinct spanning trees depends on the graph; if all edge weights are distinct, the MST is unique; equal weights can yield multiple MSTs.

Directed graphs. In directed graphs, the analogue of a spanning tree is called a spanning arborescence or branching, which is a directed tree oriented away from (or toward) a designated root.

Applications. Spanning trees are used in network design to minimize wiring costs while preserving connectivity, in broadcasting and routing, and as a tool in algorithms for clustering, reliability analysis, and circuit design.