# Non-recursive (iterative) DFS with $O(n)$ size stack

I usually deal with traversal algorithms such as DFS and BFS, and I have to implement them iteratively. However, in case of DFS, one challenge is that the size of stack can be $O(n+m)$ in worst case.

I was wondering if there is an iterative implementation of DFS that requires an $O(n)$ size stack instead of heavy $O(n+m)$ stack. I know that this is a worst case analysis, but I am concerned with this and want this to be really bounded.

Just as a reference, I am copying the algorithm from this solution, where vertices can be pushed into stack more than once and in the worst case, the stack size can be $O(n+m)$:

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
// do something with current
for each node v such that (current,v) is an edge:
s.push(v)

• Only keeping the topmost copy should work, no? Aug 4 '16 at 13:46
• @adrianN That's right, and to be honest, I already knew the answer. But I wanted this question to be here, just for people to be aware of this difference. Aug 4 '16 at 23:50

You can keep only the topmost copy of a node on the stack:

dfs(source):
s <- empty stack
visited <- {}
on_stack <- map<node,stack element>
s.push(source)
while s is not empty:
current = s.pop()
on_stack.remove(current)
if visited.contains(current):
continue
# handle current
for v a neighbor of current:
if on_stack.contains(v):
stack_element <- on_stack.get(v)
stack.push(v)


If your stack is a linked list, the asymptotic runtime stays the same. I doubt however that it will be much faster in practice unless your graphs are very dense, because the constants involved are much bigger.

• You could store references from the nodes to their entries in the stack to remove them more efficiently.
– Raphael
Aug 5 '16 at 7:56
• I do. I'll edit my answer to make it clearer. Aug 5 '16 at 7:59
• Depends what you call a stack? To me it is a linear data structure that only accesses the topmost element. Aug 5 '16 at 22:31

You can have a look on DFS-B in http://web.cs.unlv.edu/larmore/Courses/CSC477/bfsDfs.pdf

DFS-A can have multiple copies on the stack at the same time. However, the total number of iterations of the innermost loop of DFS-A cannot exceed the number of edges of G, and thus the size of S cannot exceed m. The running time of DFS-A is O(n + m). It is possible to write a DFS algorithm where no vertex is ever in the stack in more than one place, but it is somewhat trickier. We give such an algorithm, DFS-B, below.

DFS-B(G,s)
for all v in V[G] do
visited[v] := false
end for

S := EmptyStack
visited[s] := true
Push(S,s)

while not Empty(S) do
u := Pop(S)

if there is at least one unvisited vertex in Adj[u] then
Pick w to be any unvisited vertex in Adj[u]
Push(S,u)
visited[w] := true
Push(S,w)
end if
end while


I think an even better approach is the solution on C# which I developed for similar problem - https://github.com/kostadinmarinov/scc

dfs(verticies, getNeighbours):
visited <- {}

return recursiveSelect(
filter(verticies, (vertex): visited does not contain vertex),
(vertex): dfsNext(vertex, visited, getNeighbours))

dfsNext(vertex, visited, getNeighbours):

for each neighbour in getNeighbours(vertex) do
if visited does not contain neighbour then
yield neighbour
end if
end for

for each element in source do
yield element
end if
end for

recursiveSelect(source, childSelector):
stack := empty stack
enumerator := source.getEnumerator()

while enumerator has next OR stack is not empty do
if enumerator has next then
element := enumerator.current
yield element

stack.push(enumerator)
enumerator := childSelector(element).getEnumerator()
end if
else if (stack is not empty) then
enumerator := stack.pop()
end if
end while


The last method is taken from https://stackoverflow.com/a/30441479/7995961

Here the stack frame is automatically generated by the iterator's state machine which we just push in our stack. This implemented with that extension method is just a perfect generic transformer of recursive algorithms to iterative ones without changing the design of the algorithm.

PS: The above is a generic solution for any recursive algo. Here is a simplified version of the same workflow as the generic one for the specific case of DFS algo:

dfs(verticies, neighbours):
stack := empty stack
visited <- []

for each entryVertex in verticies do
if not visited[entryVertex] then
stack.push([entryVertex, -1])

while stack is not empty do (
[vertex, i] := stack.pop();

if i = -1 then
visited[vertex] := true
i := 0
end if
end while

while i < neighbours[vertex].length do
if not visited[neighbours[vertex][i]] then
stack.push([vertex, i])
stack.push([neighbours[vertex][i], -1])
break;
end if

i := i + 1
end while
end if
end for


As you see in the stack we need to keep the state of iteration also - it could be either an enumerator object or the index of a list. This is also combined with immediate interruption of the execution for the current vertex and going into the last found not visited neighbour. The state of iteration (list index) defines also 2 more states - before the loop (i = -1) and after the loop (i = n). It's very helpful in case of steps before and visiting the neighbours.

• This is not a programming site. Please replace your code with pseudocode. Sep 12 '19 at 15:08
• I hope the reworked version is fitting the pseudocode. I was not sure about things like "yield", but it's a common feature in many programming languages and means "terminate the current execution with remembering the stack and next instruction and return value". Sep 13 '19 at 10:16