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).

V2.28, 13 July 2023