Cycle Detection in Directed Graph in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in a directed graph?

A cycle in a directed graph is a path that starts and ends at the same vertex, following the direction of edges.

beginner

Which data structure is commonly used to detect cycles in a directed graph using DFS?

A recursion stack (or call stack) is used along with a visited set to detect cycles during DFS traversal.

intermediate

What does it mean if a node is found in the recursion stack during DFS?

It means a cycle is detected because the node is being visited again before the previous visit finished.

intermediate

Why can't we use a simple visited set alone to detect cycles in directed graphs?

Because a node can be visited multiple times in different paths without forming a cycle; the recursion stack helps track the current path.

advanced

Explain the role of three states: unvisited, visiting, and visited in cycle detection.

Unvisited means the node is not explored yet; visiting means the node is in the current DFS path (recursion stack); visited means the node and its descendants are fully explored. A cycle is detected if we reach a visiting node again.

What indicates a cycle during DFS in a directed graph?

A Finding a node already in the recursion stack

B Finding a node not visited before

C Finding a node with no outgoing edges

D Finding a node with only one incoming edge

A cycle is detected if a node is found in the recursion stack during DFS, meaning the path loops back.

Which of these is NOT a state used in cycle detection DFS?

A Processed

B Visiting

C Visited

D Unvisited

The common states are unvisited, visiting, and visited. 'Processed' is not a standard term here.

Why is a recursion stack needed in cycle detection for directed graphs?

A To store all visited nodes

B To count the number of edges

C To track nodes in the current path

D To sort nodes

The recursion stack tracks nodes in the current DFS path to detect cycles.

If a node is marked visited but not in recursion stack, what does it mean?

A Node is part of a cycle

B Node is fully explored with no cycle found here

C Node is unvisited

D Node is currently being explored

Visited nodes outside recursion stack are fully explored and safe from cycles in current path.

Which algorithm is commonly used for cycle detection in directed graphs?

A Dijkstra's Algorithm

B Breadth-First Search (BFS)

C Prim's Algorithm

D Depth-First Search (DFS)

DFS is commonly used for cycle detection in directed graphs.

Describe how Depth-First Search (DFS) can be used to detect a cycle in a directed graph.

Think about tracking nodes in the current path and revisiting them.

Explain why a simple visited set is not enough to detect cycles in directed graphs and how recursion stack helps.

Consider difference between nodes visited before and nodes in current exploration.

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