Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to implement depth first search for graph with a non-recursive approach

I have spent lots of time on this issue. However, I can only find solutions with non-recursive methods for a tree: Non recursive for tree, or a recursive method for the graph, Recursive for graph.

And lots of tutorials (I don't provide those links here) don't provide the approaches as well. Or the tutorial is totally incorrect. Please help me.

Updated:

It's really hard to describe:

If I have an undirected graph:

   1  / |  \ 4  |   2     3 / 

1-- 2-- 3 --1 is a cycle.

At the step: 'push the neighbors of the popped vertex into the stack', what's the order in which the vertices should be pushed?

If the pushed order is 2, 4, 3, the vertices in the stack are:

| | |3| |4| |2|      _ 

After popping the nodes, we get the result: 1 -> 3 -> 4 -> 2 instead of 1--> 3 --> 2 -->4.

It's incorrect. What condition should I add to stop this scenario?

like image 334
Alston Avatar asked Feb 02 '14 08:02

Alston


People also ask

Can you implement DFS without recursion?

Iterative Implementation of DFSThe non-recursive implementation of DFS is similar to the non-recursive implementation of BFS but differs from it in two ways: It uses a stack instead of a queue. The DFS should mark discovered only after popping the vertex, not before pushing it.

Is DFS recursive or iterative?

The only difference between iterative DFS and recursive DFS is that the recursive stack is replaced by a stack of nodes. Algorithm: Created a stack of nodes and visited array.


1 Answers

A DFS without recursion is basically the same as BFS - but use a stack instead of a queue as the data structure.

The thread Iterative DFS vs Recursive DFS and different elements order handles with both approaches and the difference between them (and there is! you will not traverse the nodes in the same order!)

The algorithm for the iterative approach is basically:

DFS(source):   s <- new stack   visited <- {} // empty set   s.push(source)   while (s is not empty):     current <- s.pop()     if (current is in visited):         continue     visited.add(current)     // do something with current     for each node v such that (current,v) is an edge:         s.push(v) 
like image 143
amit Avatar answered Sep 26 '22 01:09

amit