Spanning tree

A spanning tree of a connected graph is a tree subgraph containing every vertex. It connects all vertices without cycles and has exactly one fewer edge than vertices.

Graph theory: The mathematical study of graphs, structures made of vertices joined by edges. Spanning trees are defined as subgraphs of graphs.
Depth-first search: A graph traversal that explores one path as far as possible before backtracking. Its discovery edges form a spanning tree when the graph is connected.
Minimum spanning tree: A spanning tree of a weighted connected graph with minimum total edge weight. It selects the least-cost spanning tree when edges carry weights.
Spanning forest: A subgraph containing every vertex whose components are trees spanning the components of the original graph. It is the natural counterpart when the original graph is disconnected.
Tree (graph theory): A connected graph with no cycles. A spanning tree must itself be a tree.
Breadth-first search: A graph traversal that explores vertices in order of distance from a starting vertex. Its discovery edges form a spanning tree organized by distance layers.
Steiner tree problem: An optimization problem seeking a minimum-cost network connecting specified terminals, possibly using extra vertices. Unlike a spanning tree, it need not include every graph vertex.
Fundamental cycle: The unique cycle formed by adding one non-tree edge to a tree. Each edge outside a spanning tree creates exactly one fundamental cycle.
Connected graph: A graph in which every pair of vertices is joined by a path. A graph has a spanning tree exactly when it is connected.
Kruskal's algorithm: A greedy algorithm that builds a minimum spanning tree by adding edges in increasing weight order without creating cycles. It constructs a spanning tree by rejecting edges that would create cycles.

Linked from 9 pages