need a graph algorithm similar to DFS

Question

Hi, 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.

Answer 1

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.

Answer 2

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)

Answer 3

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