In the recursive DFS, we can detect a cycle by coloring the nodes as WHITE
, GRAY
and BLACK
as explained here.
A cycle exists if a GRAY
node is encountered during the DFS search.
My question is: When do I mark the nodes as GRAY
and BLACK
in this iterative version of DFS? (from Wikipedia)
1 procedure DFS-iterative(G,v):
2 let S be a stack
3 S.push(v)
4 while S is not empty
5 v = S.pop()
6 if v is not labeled as discovered:
7 label v as discovered
8 for all edges from v to w in G.adjacentEdges(v) do
9 S.push(w)
One option is to push each node twice to the stack along the information if you're entering or exiting it. When you pop a node from stack you check if you're entering or exiting. In case of enter color it gray, push it to stack again and advance to neighbors. In case of exit just color it black.
Here's a short Python demo which detects a cycle in a simple graph:
from collections import defaultdict
WHITE = 0
GRAY = 1
BLACK = 2
EDGES = [(0, 1), (1, 2), (0, 2), (2, 3), (3, 0)]
ENTER = 0
EXIT = 1
def create_graph(edges):
graph = defaultdict(list)
for x, y in edges:
graph[x].append(y)
return graph
def dfs_iter(graph, start):
state = {v: WHITE for v in graph}
stack = [(ENTER, start)]
while stack:
act, v = stack.pop()
if act == EXIT:
print('Exit', v)
state[v] = BLACK
else:
print('Enter', v)
state[v] = GRAY
stack.append((EXIT, v))
for n in graph[v]:
if state[n] == GRAY:
print('Found cycle at', n)
elif state[n] == WHITE:
stack.append((ENTER, n))
graph = create_graph(EDGES)
dfs_iter(graph, 0)
Output:
Enter 0
Enter 2
Enter 3
Found cycle at 0
Exit 3
Exit 2
Enter 1
Exit 1
Exit 0