need a graph algorithm similar to DFS

I'm curious if there is a specific graph algorithm that traverses an unweighted acyclic directed graph by choosing a start node and then proceeding via DFS. If a node is encountered that has unsearched predecessors then it should back track the incoming paths until all paths to start have been explored.

I found a wikipedia category for graph algorithms but there is a small sea of algorithms here and I'm not familiar with most of them.

EDIT: example: given the graph {AB, EB, BC, BD}, traverse as: {A,B,E,B,C,D} or unique order as {A,B,E,C,D}. Note this algorithm unlike BFS or DFS does not need to begin again at a new start node if all paths of the first start 开发者_开发百科node are exhausted.

In DFS, you usually choose the vertex to be visited after u based on the edges starting at u. You want to choose based first on the edges ending at u. To do this, you could have a transpose graph info, and try to get the vertex from there first.

It would be something like this:

procedure dfs(vertex u)
  mark u as visited
  for each edge (v, u) //found in transpose graph
    if v not visited
      dfs(v)
  for each edge (u, w)
    if v not visited
      dfs(w)

What you are looking for is the topological sort. As far as I'm aware there's no easy way to traverse a graph in its topologically sorted order without any precomputation.

The standard way to get the topsort is to do a standard DFS, and then store the visited nodes in order of their visiting times. Finally, reverse those nodes and voila, you have them in the order you desire.

Pseudocode:

list topsort

procedure dfs(vertex u)
  mark u as visited
  for each edge (u, v)
    if v not visited
      dfs(v)
  add u to the back of topsort

The list topsort will then contain the vertices in the reverse order that you want. Just reverse the elements of topsort to correct that.

If you're looking for topological sort, you can also do this, given an adjacency list (or a list of edges (u,v) which you can preprocess in O(E) time):

list top_sort( graph in adjacency list )
     parent = new list
     queue = new queue
     for each u in nodes
         parent(u) = number of parents
         if ( parent(u) is 0 ) // nothing points to node i
             queue.enqueue( u )

     while ( queue is not empty )
         u = queue.pop
         add u to visited
         for each edge ( u, v )
             decrement parent(v) // children all have one less parent
             if ( parent(v) is 0 )
                 queue.enqueue( v )

Given an adjacency list (or a list of edges (u,v)), this is O( V + E ), since each edge is touched twice - once to increment, once to decrement, in O(1) time each. With a normal queue, each vertice will also be processed by the queue at most twice - which can be done also in O(1) with a standard queue.

Note that this differs from the DFS (at least a straight-up implementation) in that it handles forests.

Another interesting note is that if you substitute queue with a priority_queue imposing some sort of structure/ordering, you can actually return the results sorted in some order.

For example, for a canonical class dependency graph (you can only take class X if you took class Y):

100:
101: 100
200: 100 101
201: 
202: 201

you would probably get, as a result:

100, 201, 101, 202, 200

but if you change it so that you always want to take lower numbered classes first, you can easily change it to return:

100, 101, 200, 201, 202