Cycle Detection in Directed Graph in DSA Python - Execution Trace

Concept Flow - Cycle Detection in Directed Graph

Start at each unvisited node

↓

Mark node as visiting

↓

For each neighbor

↓

Is neighbor visiting?

Yes→Cycle found

No↓

Is neighbor visited?

No→DFS on neighbor

↓

Mark node as visited

↓

Done

Start DFS from each unvisited node, mark nodes as visiting during traversal, detect cycle if a visiting node is revisited, mark visited when done.

Execution Sample

DSA Python

def dfs(node):
    visiting[node] = True
    for neighbor in graph[node]:
        if visiting.get(neighbor, False):
            return True
        if not visited.get(neighbor, False):
            if dfs(neighbor):
                return True
    visiting[node] = False
    visited[node] = True
    return False

This code runs DFS to detect if a cycle exists by tracking visiting and visited nodes.

Execution Table

Step	Operation	Current Node	Visiting Set	Visited Set	Action	Cycle Detected	Visual State
1	Start DFS	A	{A}	{}	Mark A visiting	No	A(visiting)
2	Explore neighbor	A	{A}	{}	Check neighbor B	No	A(visiting) -> B(unvisited)
3	Start DFS	B	{A,B}	{}	Mark B visiting	No	A(visiting) -> B(visiting)
4	Explore neighbor	B	{A,B}	{}	Check neighbor C	No	A(visiting) -> B(visiting) -> C(unvisited)
5	Start DFS	C	{A,B,C}	{}	Mark C visiting	No	A(visiting) -> B(visiting) -> C(visiting)
6	Explore neighbor	C	{A,B,C}	{}	Check neighbor A	Yes	Cycle detected at A(visiting)
7	Return True	C	{A,B,C}	{}	Cycle found, return True	Yes	Cycle detected
8	Return True	B	{A,B,C}	{}	Cycle found, return True	Yes	Cycle detected
9	Return True	A	{A,B,C}	{}	Cycle found, return True	Yes	Cycle detected
10	Stop	-	-	-	Cycle detected, stop search	Yes	Cycle detected in graph

💡 Cycle detected when visiting node A again while it is still in visiting set

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 6	Final
visiting	{}	{A}	{A,B}	{A,B,C}	{A,B,C}	{A,B,C}
visited	{}	{}	{}	{}	{}	{}
current_node	None	A	B	C	C	None
cycle_detected	False	False	False	False	True	True

Key Moments - 3 Insights

Why do we mark nodes as 'visiting' before exploring neighbors?

Marking nodes as 'visiting' helps detect cycles by identifying if we revisit a node currently in the recursion stack, as shown in step 6 where revisiting A(visiting) detects a cycle.

Why do we check if a neighbor is already 'visited' before DFS?

If a neighbor is 'visited', it means it and its descendants have been fully explored without cycles, so we skip DFS to avoid redundant work, as seen in steps where visited set is checked.

What causes the cycle detection to stop the search?

When a neighbor is found in the 'visiting' set (step 6), it means a cycle exists, so the function returns True immediately, stopping further search as shown in steps 7-10.

Visual Quiz - 3 Questions

Look at the execution table, what is the visiting set after step 3?

A {A, B}

B {A}

C {}

D {B}

💡 Hint

Check the 'Visiting Set' column at step 3 in the execution table.

At which step is the cycle first detected?

A Step 5

B Step 6

C Step 7

D Step 4

💡 Hint

Look for 'Cycle detected' in the 'Cycle Detected' column in the execution table.

If the graph had no cycle, what would happen to the visiting set at the end?

A It would contain only the start node

B It would contain all nodes

C It would be empty

D It would contain nodes visited last

💡 Hint

Refer to the 'visiting' variable in variable_tracker showing it becomes empty after DFS completes.

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Use two sets: visiting (nodes in current path) and visited (fully explored nodes).
- Start DFS from each unvisited node.
- Mark node as visiting before exploring neighbors.
- If neighbor is visiting, cycle detected.
- After exploring neighbors, mark node visited.
- Stop search immediately when cycle found.

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS) with two sets: visiting and visited. We start DFS from each unvisited node, marking it as visiting. For each neighbor, if it is already visiting, a cycle is detected. If not visited, we DFS on it. After all neighbors are explored, we mark the node as visited. The search stops immediately when a cycle is found. This method ensures we detect cycles by tracking nodes currently in the recursion stack.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. The total number of nodes in the graph

B. The shortest path between two nodes

C. The maximum degree of any node

D. Whether there is a path that starts and ends at the same node following the direction of edges

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means starting from a node and following directed edges, you can return to the same node.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following the direction of edges -> Option D

4. Quick Check:

   Cycle detection = path returning to start node [OK]

Hint: Cycle means path loops back to start node following edges [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated node without direction

2. Which Python data structure is commonly used to keep track of nodes currently in the recursion stack during cycle detection in a directed graph?

easy

A. Set

B. List

C. Dictionary

D. Queue

Solution

1. Step 1: Identify recursion stack tracking

   During DFS, nodes currently being explored are tracked to detect cycles.

2. Step 2: Choose data structure for fast membership check

   Set allows O(1) check if a node is in recursion stack.

3. Final Answer:

   Set -> Option A

4. Quick Check:

   Recursion stack uses set for fast lookup [OK]

Hint: Use set for fast check if node is in recursion stack [OK]

Common Mistakes:

• Using list which is slower for membership check
• Using queue which is FIFO, not suitable here
• Using dictionary without keys for membership

3. What will be the output of the following code snippet?

graph = {0: [1], 1: [2], 2: [0]}
visited = set()
rec_stack = set()
def dfs(node):
    if node in rec_stack:
        return True
    if node in visited:
        return False
    visited.add(node)
    rec_stack.add(node)
    for neighbor in graph.get(node, []):
        if dfs(neighbor):
            return True
    rec_stack.remove(node)
    return False

print(dfs(0))

medium

A. True

B. False

C. None

D. Error

Solution

1. Step 1: Trace DFS calls starting from node 0

   Node 0 calls dfs(1), which calls dfs(2), which calls dfs(0) again.

2. Step 2: Detect cycle when node 0 is in recursion stack

   When dfs(0) is called second time, node 0 is in rec_stack, so returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Cycle detected = True [OK]

Hint: Cycle if node revisited in recursion stack returns True [OK]

Common Mistakes:

• Ignoring recursion stack check
• Confusing visited with recursion stack
• Assuming no cycle returns True

4. Find the bug in this cycle detection code snippet for a directed graph:

def dfs(node, graph, visited, rec_stack):
    visited.add(node)
    rec_stack.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, graph, visited, rec_stack)
        elif neighbor in rec_stack:
            return True
    rec_stack.remove(node)
    return False

medium

A. Should use list instead of set for rec_stack

B. Missing return value when dfs(neighbor) is called recursively

C. Visited set should be cleared after recursion

D. Graph keys should be integers only

Solution

1. Step 1: Check recursive call return usage

   The recursive call dfs(neighbor, ...) is made but its return value is ignored.

2. Step 2: Fix by returning True if recursive call finds cycle

   Should return True immediately if dfs(neighbor, ...) returns True.

3. Final Answer:

   Missing return value when dfs(neighbor) is called recursively -> Option B

4. Quick Check:

   Return True on recursive cycle detection [OK]

Hint: Return True immediately when recursive call detects cycle [OK]

Common Mistakes:

• Ignoring recursive call return value
• Using wrong data structure for rec_stack
• Clearing visited incorrectly

5. Given a directed graph represented as adjacency list:

graph = {
  'A': ['B'],
  'B': ['C', 'D'],
  'C': ['E'],
  'D': ['F'],
  'E': ['B'],
  'F': []
}

Which nodes are part of at least one cycle?

hard

A. A, D, F

B. A, B, C, E

C. B, C, E

D. No nodes form a cycle

Solution

1. Step 1: Identify cycles by tracing edges

   Path B -> C -> E -> B forms a cycle involving B, C, E.

2. Step 2: Check other nodes

   A leads to B but is not in cycle; D and F have no cycles.

3. Final Answer:

   B, C, E -> Option C

4. Quick Check:

   Cycle nodes = B, C, E [OK]

Hint: Trace edges to find nodes revisited in cycle [OK]

Common Mistakes:

• Including nodes only leading to cycle but not in it
• Ignoring indirect cycles
• Assuming all connected nodes form cycles