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
You could do that simply by not popping the stack element right away.
For every iteration, do v = stack.peek()
and if v
is White
, mark it as Grey
and go ahead exploring its neighbours.
However, if v
is Grey, it means that you have encountered v
for the second time in the stack and you have completed exploring it. Mark it Black
and continue the loop.
Here's how your modified code should look like:
procedure DFS-iterative(G,v):
let S be a stack
S.push(v)
while S is not empty
v = S.peek()
if v is not labeled as Grey:
label v as Grey
for all edges from v to w in G.adjacentEdges(v) do
if w is labeled White do
S.push(w)
elif w is labeled Grey do
return False # Cycle detected
# if w is black, it's already explored so ignore
elif v is labeled as Grey:
S.pop() # Remove the stack element as it has been explored
label v as Black
If you're using a visited
list to mark all visited nodes and another recStack
i.e a list which keeps track of nodes currently being explored, then what you can do is, instead of popping the element from stack, just do stack.peek()
. If the element is not visited (it means you're encountering that element for the first time in the stack), just mark it True
in visited
and recStack
and explore its children.
However, if the peek()
value is already visited, it means you're ending the exploration of that node so just pop it and make it's recStack
as False again.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With