Running the Depth First Search (DFS) algorithm over a given graph G = (V,E) which is connected and undirected provides a spanning tree. While running DFS on the graph, when we arrive to a vertex which it's degree is greater than 1 , i.e - there is more than one edge connected to it , we randomly choose an edge to continue with. I'd like to know if the option to choose an edge (or a vertex) to continue with actually allows as to create every spanning tree of a given graph using DFS?
Since you mentioned in the comments that given a spanning tree you want some DFS that outputs the same tree, This shouldn't be a problem.
Suppose you have the required spanning tree and the graph in the form of an adjacency list and have a method edge_exists(u,v) which returns true or false depending on whether the edge is present or not in the given spanning tree.
explore(node):
visited[node] = 1;
for v in node.neighbors:
if edge_exists(node, v) && !visited[v]:
v.p = node
explore(v)
BTW i don't think you need to do a visited count since you have a spanning tree, so edge_exisits will do roughly the same for you
By programmatically outputting the spanning tree, I meant, given a graph output all the spanning trees. I am not sure how to do this.