Reputation: 13424
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.
Upvotes: 2
Views: 1622
Reputation: 4579
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
Upvotes: 2
Reputation: 17949
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)
Upvotes: 2
Reputation: 54310
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.
Upvotes: 2