# Iterative Depth First Search for cycle detection on directed graphs

I found this pseudocode on Wikipedia, and looks very elegant and intuitive:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)

function visit(node n)
if n has a permanent mark then
return
if n has a temporary mark then
stop   (not a DAG)

mark n with a temporary mark

for each node m with an edge from n to m do
visit(m)

remove temporary mark from n
mark n with a permanent mark


I am trying to write an iterative version for this using 3 marks (UNVISITED, VISITED, PROCESSED), but the lack of tail recursion really bothers me.

How should I approach this?

• Why do you think that lack of tail recursion might be wrong? – Rick Decker Mar 16 at 23:27
• In general, turning recursive procedures into iterative ones is as simple as using a stack explicitly. Then simply run a while (not empty stack), pop at the beginning of the body and push at the end, and there you go ... ! – Carlos Linares López Mar 16 at 23:28
• @CarlosLinaresLópez That approach works but I'm not quire sure I agree on "is as simple as". In general, the recursive calls might happen in the middle of the parent function, and their parameters could even depend on the results of the previous calls. This requires storing the position and the state (i.e., local variables) of the parent call in the stack as well, in order to resume its execution (in a way you are simulating jumping to the return address of the caller). – Steven Mar 16 at 23:36
• @Steven: that is absolutely true in the general case, but the basic form of depth-first search is implemented with tail recursion which significantly simplifies the implementation with a simple stack – Carlos Linares López Mar 17 at 11:21

You could add "colors" to the nodes similar to the method done for recursive DFS found in CLRS, for example. When you instantiate each node (assuming they are objects) put a color field such that every node initially has node.color $$\xleftarrow{}$$ white.

The following is your pseudocode modified that I believe would help:

    L ← Empty list of all nodes, where node.color ← black (once placed here)
while exists nodes such that node.color is white do
select a node n such that n.color is white
visit(n)

function visit(node n)
if n.color is black then:
return
if n.color is gray then:
stop   (back edge is found indicates cycle exists)

mark n.color as gray

for each node m with an edge from n to m do
visit(m)

mark n.color as black


The idea is that all "unvisited" nodes begin colored "white". Then, when we encounter a node, we visit it and color it "grey" while exploring it. When we are done exploring this node, we color it "black". We only call DFS on nodes with "white" color.

Also regarding implementation, in addition to the stack, you could make L a set and just do a check on the size (since you know only distinct nodes will get added to this set) and once the size is equal to the number of nodes you know you've visited all the nodes of the graph, but as is if you use the coloring eventually it'll be the case that there is no node, n such that n.color == white.

Using the same logic as the recursive algorithm, I added on the stack a pos value which keeps track of the position of the last descendant currently processing.

This was necessary for the "backtrack" steps of the algorithm.

from typing import List

UNDISCOVERED = -1
DISCOVERED = 0
PROCESSED = 1

def is_acyclic(graph: List[list], vertex_count: int) -> bool:
state = [UNDISCOVERED] * vertex_count
for vertex in range(vertex_count):
if not dfs(graph, vertex, state):
return False

return True

def dfs(graph: List[list], v: int, state: list) -> bool:
stack = [(v, 0)]
while stack:
curr, pos = stack[-1]
if state[curr] == PROCESSED:
stack.pop()
continue
if state[curr] == DISCOVERED and pos == 0:
return False
if pos == 0:
state[curr] = DISCOVERED

for i in range(pos, len(graph[curr])):
stack[-1] = curr, pos + 1
descendant = graph[curr][i]
stack.append((descendant, 0))
break
else:
state[curr] = PROCESSED

return True