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.

Tapp

I haven't done a lot of them, but I find stack-based solutions to recursive problems to be generally messy. I'd just have been glad to have gotten it working. – Marchelle

I don't really see why you need visited + done (just replace if S.peek().done == True with if S.peek().visited == True). In your example, you wouldn't process C twice, since you'd set visited = True when processing C from D. – Marchelle

Can I ask, why do you want to avoid recursion? Many modern CPUs have optization that allow some recursive algorithms to outperform their non-recursive counterparts. – Lagos

Dukeling, if you only set visited to True at that point, then you can actually get infinite loops. In my algorithm, you only set done to True when ascending, so if you only set visited to True at that point and you have a loop in the graph, you will keep loading things on the stack (because the children will only be marked visited once all their children are ascended, but their children can't ascend until their children ascend... etc). – Tapp

500, the problem is that not so much speed as storage. If you have an explicit stack, then without breaking a sweat you can have a depth equal to the size of your RAM. The maximum stack size on recursion is much smaller, I've heard numbers like 8mb. Languages like Python have a default maximum recursion depth of 1000 (can be changed). For a DFS your max stack size is often the number of nodes in the graph, for which say 10 000 isn't particularly large. Whereas in say merge sort, you are guaranteed max recursion depth of log(n), where n is size of sorted array. So you're safe. – Tapp

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.

Marchelle

That is a pretty cool idea. As given, I'm not sure how it would handle the unwinding stage. Since you are only pushing iterators on, then only have access to the children at a given time. When you discover that the iterator has no more children, you need to access the original node.But, I think if you push the nodes themselves on but use the node's iterator then you could do it nicely. At the end of the day though, this is even more storage in exchange for slightly more speed/elegance. Recursively you don't need any of this stuff. Is there not an even better way? – Tapp

Edited. @Nir Consider with your algorithm you push all (unvisited) children for a given node onto the stack, but with this you only push an iterator onto the stack, thus it's likely less storage. The recursive algorithm essentially does the same (although the programmer doesn't have to handle it) - at each recursive step you store all local variables, which includes at least a node and the position in the children array. – Marchelle

It's a little tricky working through the indirection, but it seems like the iterator is still more space. Either way, you have to have read in the nodes, and lists of pointers to their children. Either way, the stack is just storing pointers. But the iterator itself is another pointer that is not needed in my code. Basically the iterator is a way to resume the for loop that I use to load the children in the middle. So it couldn't possibly store less than an integer (more than 3 bits), and in practice probably stores 2 pointers and an integer (beginning, current ,beginning + size). – Tapp

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).

Subjunction

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)

Vicenta

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.

Jedlicka

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.
      }
    }
  }
}

Tonne

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.

Slyviasm

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.

Ader

You didn't address the problem, the challenge is correct behavior on winding and unwinding, and you did not discuss this aspect at all. In a recursive implementation, you control this winding/unwinding simply by putting code before or after the recursive call. In your implementation, the root gets processed first. Thus, it represents the winding. What about the unwinding? In a recursive implementation, the last piece of code to run is the code after the recursive call, on the root. In your implementation, code cannot be called on root at the end. – Tapp