Non-recursive DFS implementation
I recently needed to implement non-recursive DFS as part of a more complex 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 difficult it was, and I wondered if I had done anything wrong.
There are two main approaches to iterative DFS. First, you can push all the children of a node onto the stack at once (seems much more common). Or you can just click on it. I'll focus on the first one as it seems like everyone is doing it.
I had various problems with this algorithm, and in the end I realized that in order to use it efficiently I need not 1, not 2, but 3 boolean flags (I don't necessarily want you to need three explicit boolean variables, information is indirectly via special variable values, which are usually integers, but you need to access these 3 pieces of information anyway Three flags were: 1) visited. This was done in order to prevent children from getting too much in the pile. 2) Done. To avoid redundant processing of the same node. 3) Upward / downward. To indicate if children have 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 an upward / downward technical relationship as you can just see if all the kids are done or not. But this is rather inefficient in a dense graph.
2) Main kicker: The thing visited / done may seem unnecessary. This is why (I think) you need it. You can't mark things you've visited until you put them on the stack. If you do this, you may be handling things in the wrong order. For example. suppose A is connected to B and C, B is connected to D and D is connected to C. Then from A, you push B and C onto the stack. From B, you push D on the stack ... and then what? If you mark things visited when you push them onto the stack, you won't push C onto the stack here. But this is wrong, C should be visited from D and not from A on this graph (assuming A visits B before C). This way, you don't mark the things you have visited until you have processed them. But then you will have C on the stack twice. Therefore, you need another flag to show that you have completely mastered it,so you don't process C a second time.
I don't see how to avoid all of this in order to have a perfectly correct non-recursive DFS that supports both winding and unwinding actions. But instinctively, he feels cool. Is there a better way? Almost every place I have consulted on the Internet is really silent on how to actually implement non-recursive DFS, stating that it can be done and provide a very simple algorithm. When an algorithm is correct (in terms of correctly supporting multiple paths to the same node), which is sparse, it rarely properly supports winding and unwinding.
source to share
I think the most elegant stack based implementation would have iterators of the children on the stack, not nodes. Think of an iterator as storing node and 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 can be optimized to store ito space by splitting node and position into 2 stacks.
source to share
Your code doesn't completely mimic what happens with a recursive DFS implementation. In a recursive DFS implementation, each node appears only once on the stack at any time.
The solution given by Dukeling is a way to do it iteratively. Basically, you should only be pushing one node at a time on the stack, not all at once.
Your statement that this will require more memory is not correct: with your implementation, node can be multiple times on the stack. In fact, if you start with a very dense graph (full graph at all vertices) this will happen. With Dukeling's solution, the stack size is O (number of vertices). In your solution, this is O (number of edges).
source to share
BFS Algorithm (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
DFS Algorithm (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)
source to share
Tl; dr is that you don't need more than one flag.
Indeed, you can convert recursive DFS to iterative by explicitly doing what the runtime stack compiler does. It is used goto
in the method to simulate call and return, but they can be converted to more readable loops. I'll work in C because you can compile 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 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" of the code to start getting rid of goto
s.
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;
}
}
Continue converting and we're done 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 normal. There is one more optional step "polish". We can pop the root off the stack first 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;
}
}
}
}
It's pretty obvious at this point that you are actually using a stack of iterators: a pointer to a node and an index that reflects the current progress when looking for that node's children. With a language like Java, we can make this explicit. (The downside is that we lose access to the parent process when processing children, which can be a problem in some cases.)
Here I will use a separate collection for storing visited nodes. This is much preferred because it makes more than one search and partial searches much easier.
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 can skip pushing the deprecated iterators on the stack (in C values, i
at the end of the array child
), since they are simply ignored once they appear.
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.
}
}
}
}
source to share
To do DFS traversal using the stack, push a node off the stack (remember to push the starting node on the stack) and check if it's already visited. If you have already visited, then ignore and click Next, otherwise output a pop-ed node, mark it with a visit and pop all its neighbors onto the stack. Keep doing this until the stack is empty.
source to share