Non-Recursive DFS Implementation

Question

Recently I needed to implement non-recursive DFS as part of a more complicated algorithm, Tarjan's algorithm to be precise. The recursive implementation is very elegant, but not suitable for large graphs. When I implemented the iterative version, I was shocked at how inelegant it finally ended up being, and I was wondering if I had done something wrong.

There's two basic approaches to iterative DFS. First, you can push all the children of a node at once onto the stack (seems by far more common). Or you can just push one. I will focus on the first one as that seems how everyone does it.

I had various problems with this algorithm, and eventually I realized that to do it efficiently, I needed not 1, not 2, but 3 boolean flags (I don't necessarily mean you need three explicit boolean variables, you might store the information indirectly via special values of variables that are usually integers, but you need to access those 3 pieces of information one way or another. The three flags were: 1) visited. This was to prevent children from being pushed onto the stack very redundantly. 2) Done. To prevent redundant processing of the same node. 3) Ascending/descending. To indicate whether the children had already been pushed onto the stack. The pseudocode looks something like this:

while(S)
    if S.peek().done == True
        S.pop()
        continue

    S.peek().visited = True

    if S.peek().descending == True
        S.peek().descending = False
        for c in S.peek().children
            if c.visited == False
                S.push(c)
        doDescendingStuff()    
    else
        w = S.pop()
        w.done = True
        doAscendingStuff()

Some notes: 1) You don't need ascending/descending technically, as you could just see if the children are all done or not. But it's pretty inefficient in a dense graph.

2), The main kicker: The visited/done thing might not seem necessary. Here's why (I think) you need it. You can't mark things visited until you visit them on the stack. If you do, you can process things in the wrong order. E.g. suppose A is linked to B and C, B links to D, and D links to C. Then from A, you will push B and C on the stack. From B you push D on the stack... and then what? If you are marking things visited when you push them on the stack, you won't push C on the stack here. But this is wrong, C should be visited from D, not from A in this graph (assuming that A visits B before C). So, you don't mark things visited until you process them. But then, you will have C on the stack twice. So you need another flag to show you are completely done with it, so you don't process C a second time.

I don't see how to avoid all this to having a perfectly correct non-recursive DFS that supports actions both winding and unwinding. But instinctively it feels crufty. Is there a better way? Almost every place that I have consulted online really glosses over how to actually implement non-recursive DFS, saying that it can be done and providing a very basic algorithm. When the algorithm is correct (in terms of properly supporting multiple paths to the same node) which is rare, it rarely properly supports doing stuff both on winding and unwinding.

Answer 1

I think the most elegant stack-based implementation would have iterators of children on the stack, rather than nodes. Think of an iterator just as storing a node and a position in its children.

while (!S.empty)
  Iterator i = S.pop()
  bool found = false
  Iterator temp = null
  while (i.hasNext())
    Node n = i.next()
    if (n.visited == false)
      n.visited = true
      doDescendingStuff(n)
      temp = n.getChildrenIterator()
      break
  if (!i.hasNext())
    doAscendingStuff(i.getNode())
  else
    S.push(i)
  if (temp != null)
    S.push(temp)

The above could be optimised i.t.o storage space by separating the node and position onto 2 stacks.

Answer 2

Your code does not fully emulate what happens with the recursive DFS implementation. In the recursive DFS implementation, every node appears only once in the stack at any time.

The solution given by Dukeling is a way to do it iteratively. Basically, you have to push only one node at a time in the stack, instead of all at once.

Your assertion that this would need more storage is wrong: with your implementation, a node can be multiple times on a stack. In fact, if you start from a very dense graph (the complete graph on all vertices) this WILL happen. With Dukeling solution, the size of the stack is O(number of vertices). In your solution, it is O(number of edges).

Answer 3

Algorithm BFS(G, v)

enqueue(Q, v)
mark v as visited

while Q is not empty do
    let w = front(Q)
    visit(w)
    dequeue(Q)

    for each vertex u adjacent to w do
        if u is not marked
            enqueue(Q, u)
            mark u as visited

Algorithm DFS(G, v)

push(S, v)
mark v as visited
visit(v)

while S is not empty do
    let w = top(S)
    pop(S)

    find the first umarked vertex u that is adjacent to w 

    if found such vertex u
        push(S, u)
        mark u as visited
        visit(u)

    else if not found such vertex u
        pop(S)

Answer 4

Robert Sedgewick's algorithms in cpp book talks about a special stack that only keeps one copy of an item, and forgets the old copy. Not entirely sure about how to do this, but it eliminates the problem of having multiple items in the stack.

Answer 5

Tl;dr is that you don't need more than one flag.

Indeed you can transform the recursive DFS to iterative by doing explicitly what the compiler does with the runtime stack. The technique uses gotos to simulate call and return, but these can be transformed to more readable loops. I'll work in C because you can actually compile the intermediate results:

#include <stdio.h>
#include <stdlib.h>
#define ARITY 4

typedef struct node_s {
  struct node_s *child[ARITY];
  int visited_p;
} NODE;

// Recursive version.
void dfs(NODE *p) {
  p->visited_p = 1;
  for (int i = 0; i < ARITY; ++i)
    if (p->child[i] && !p->child[i]->visited_p)
      dfs(p->child[i]);
}

// Model of the compiler's stack frame.
typedef struct stack_frame_s {
  int i;
  NODE *p;
} STACK_FRAME;

// First iterative version.
void idfs1(NODE *p) {
 // Set up the stack.
 STACK_FRAME stack[100];
 int i, sp = 0;
 // Recursive calls will jump back here.
 start:
  p->visited_p = 1;
  // Simplify by using a while rather than for loop.
  i = 0;
  while (i < ARITY) {
    if (p->child[i] && !p->child[i]->visited_p) {        
      stack[sp].i = i;   // Save params and locals to stack.
      stack[sp++].p = p;
      p = p->child[i];   // Update the param to its new value.
      goto start;        // Emulate the recursive call.
      rtn: ;             // Emulate the recursive return.
    }
    ++i;
  }
  // Emulate restoring the previous stack frame if there is one.
  if (sp) {
    i = stack[--sp].i;
    p = stack[sp].p;
    goto rtn;   // Return from previous call.
  }
}

Now do some "algebra" on the code to start getting rid of gotos.

void idfs2(NODE *p) {
 STACK_FRAME stack[100];
 int i, sp = 0;
 start:
  p->visited_p = 1;
  i = 0;
  loop:
  while (i < ARITY) {
    if (p->child[i] && !p->child[i]->visited_p) {
      stack[sp].i = i;
      stack[sp++].p = p;
      p = p->child[i];
      goto start;
    }
    ++i;
  }
  if (sp) {
    i = stack[--sp].i + 1;
    p = stack[sp].p;
    goto loop;
  }
}

Keep transforming, and we end up here:

void idfs3(NODE *p) {
  STACK_FRAME stack[100];
  int i, sp = 0;
  p->visited_p = 1;
  i = 0;
  for (;;) {
    while (i < ARITY) {
      if (p->child[i] && !p->child[i]->visited_p) {
        stack[sp].i = i; 
        stack[sp++].p = p;
        p = p->child[i];
        p->visited_p = 1;
        i = 0;
      } else {
        ++i;
      }
    }
    if (!sp) break;
    i = stack[--sp].i + 1; 
    p = stack[sp].p;
  }
}

This is fine. There's one more optional "polish" step. We can push the root on the stack initially to simplify the outer loop a bit:

void idfs3(NODE *p) {
  STACK_FRAME stack[100];
  p->visited_p = 1;
  stack[0].i = 0
  stack[0].p = p;
  int sp = 1;
  while (sp > 0) {
    int i = stack[--sp].i; 
    p = stack[sp].p;
    while (i < ARITY) {
      if (p->child[i] && !p->child[i]->visited_p) {
        stack[sp].i = i + 1; 
        stack[sp++].p = p;
        p = p->child[i];
        p->visited_p = 1;
        i = 0;
      } else {
        ++i;
      }
    }
  }
}

At this point it's pretty obvious that you really are using a stack of iterators: a pointer to node and the index that reflects current progress on searching that node's children. With a language like Java, we can make this explicit. (A down side is that we lose access to the parent while processing the children, which might be an issue in some cases.)

Here I'll use a separate set to keep the visited nodes. This is much preferred, since it makes more than one search and partial searches much simpler.

void search(Node p) {
  Set<Node> visited = new HashSet<>();
  Deque<Iterator<Node>> stack = new ArrayDeque<>();
  visited.add(p); // Visit the root.
  stack.push(p.children.iterator());
  while (!stack.isEmpty()) {
    Iterator<Node> i = stack.pop(); // Backtrack to a child list with work to do.
    while (i.hasNext()) {
      Node child = i.next(); 
      if (!visited.contains(child)) {
        stack.push(i);  // Save progress on this child list.
        visited.add(child); // Descend to visit the child.
        i = child.children.iterator(); // Process its children next.
      }
    }
  }
}

As a final micro-optimization, you could skip pushing exhausted iterators on the stack (in C, i values at the end of the child array), since they're just ignored after popping.

void search(Node p) {
  Set<Node> visited = new HashSet<>();
  Deque<Iterator<Node>> stack = new ArrayDeque<>();
  visited.add(p); // Visit the root.
  if (!p.children.isEmpty()) stack.push(p.children.iterator());
  while (!stack.isEmpty()) {
    Iterator<Node> i = stack.pop(); // Backtrack to a child list with work to do.
    while (i.hasNext()) {
      Node child = i.next(); 
      if (!visited.contains(child)) {
        if (i.hasNext()) stack.push(i);  // Save progress on this child list.
        visited.add(child); // Descend to visit the child.
        i = child.children.iterator(); // Process its children next.
      }
    }
  }
}

Answer 6

Here is a link to a java program showing DFS following both reccursive and non-reccursive methods and also calculating discovery and finish time, but no edge laleling.

    public void DFSIterative() {
    Reset();
    Stack<Vertex> s = new Stack<>();
    for (Vertex v : vertices.values()) {
        if (!v.visited) {
            v.d = ++time;
            v.visited = true;
            s.push(v);
            while (!s.isEmpty()) {
                Vertex u = s.peek();
                s.pop();
                boolean bFinished = true;
                for (Vertex w : u.adj) {
                    if (!w.visited) {
                        w.visited = true;
                        w.d = ++time;
                        w.p = u;
                        s.push(w);
                        bFinished = false;
                        break;
                    }
                }
                if (bFinished) {
                    u.f = ++time;
                    if (u.p != null)
                        s.push(u.p);
                }
            }
        }
    }
}

Full source here. Also this is a nice video explainging DFS.

Answer 7

In order to do DFS traversal using stack, pop a node from stack (remember to push the initial node in stack) and check if it is already visited. If already visited then ignore and pop next, else output the pop-ed node, mark it visited and push all its neighbors onto stack. Keep doing that until the stack is empty.