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

Question

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?

Answer 1

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)