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