Spanning Tree

Let G be a simple graph. A spanning tree of G is a subgraph of G that is a tree containing every vertex of G.

A simple graph is connected IFF it has a spanning tree.

A spanning tree can be constructed using either depth-first search (a.k.a. backtracking) or breadth-first search.

References