Spanning Trees of a Graph or Digraph

SpanningForest(G) : Grph -> Grph

Given a graph G, construct a spanning forest for G. The forest is returned as a subgraph of G.

SpanningTree(G) : Grph -> Grph

Given a connected 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.

BreadthFirstSearchTree(u) : GrphVert -> Grph

BFSTree(u) : GrphVert -> Grph

Given a vertex u belonging to the connected graph G, return a breadth-first search spanning tree for G rooted at the vertex u. The spanning tree is returned as a subgraph of G.

DepthFirstSearchTree(u) : GrphVert -> Grph

DFSTree(u) : GrphVert -> Grph

Given a vertex u belonging to the connected graph G, return a depth-first search spanning tree for G rooted at the vertex u. The spanning tree is returned as a subgraph of G.