# Spanning Trees of a Graph or Digraph

## `SpanningTree(G): GrphUnd -> Grph, GrphVertSet, GrphEdgeSet`

Given a connected (undirected) graph $G$, construct a spanning tree for $G$ rooted at an arbitrary vertex of $G$. The spanning tree is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

## `SpanningForest(G): Grph -> Grph, GrphVertSet, GrphEdgeSet`

Given a graph $G$, construct a spanning forest for $G$. The forest is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph.

## `BreadthFirstSearchTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet`

## `BFSTree(u): GrphVert -> Grph`

Given a vertex $u$ belonging to the graph $G$, return a breadth-first search for $G$ rooted at the vertex $u$. The tree is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph. Note that $G$ may be disconnected.

## `DepthFirstSearchTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum`

## `DFSTree(u): GrphVert -> Grph, GrphVertSet, GrphEdgeSet, SeqEnum`

Given a vertex $u$ belonging to the graph $G$, return a depth-first search tree $T$ for $G$ rooted at the vertex $u$. The tree $T$ is returned as a subgraph of $G$. The support and vertex/edge decorations are *not* retained in the resulting (structural) subgraph. Note that $G$ may be disconnected.

The fourth return argument returns, for each vertex $u$ of $G$, the tree order of $u$, that is, the order in which the vertex $u$ has been visited while performing the depth-first search. If $T$ does not span $G$ then the vertices of $G$ not in $T$ are given tree order from `Order(T) + 1` to `Order(G)`.