All the trees returned by the functions described below are returned as structural subgraphs of the original graph whose support and vertex and edge decorations are not retained in the resulting tree.
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 structural subgraph of G, without the support, vertex or edge decorations of G.
Given a graph G, construct a spanning forest for G. The forest is returned as a structural subgraph of G, without the support, vertex or edge decorations of G.
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 structural subgraph of G, without the support, vertex or edge decorations of G. Note that G may be disconnected.
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 structural subgraph of G, without the support, vertex or edge decorations of G. 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).