spanning tree

For a connected graph , the spanning trees of is a subgraph that is a tree which contains all of the vertices of .

A connected graph will contain at least one spanning tree, and a graph not connected will not contain a spanning tree (but instead contains spanning forests).

Depth-first search and breadth-first search are ways to find a spanning tree of a graph.

In the context of weighted graphs, one would prefer a minimal spanning tree.