MAGMA Computational Algebra System

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