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