Cycle Detection in Directed Graph in DSA Python - Build from Scratch

Cycle Detection in Directed Graph

📖 Scenario: Imagine you are working on a project management tool. Tasks depend on other tasks to be completed first. If there is a circular dependency, the project cannot proceed. You need to detect if such a cycle exists in the task dependencies.

🎯 Goal: Build a program to detect if a directed graph (task dependencies) contains a cycle using depth-first search.

📋 What You'll Learn

Create a directed graph using a dictionary where keys are task names and values are lists of dependent tasks.

Create two sets to track visited tasks and tasks in the current recursion stack.

Implement a function to perform depth-first search and detect cycles.

Print true if a cycle exists, otherwise false.

💡 Why This Matters

🌍 Real World

Detecting cycles in task dependencies helps avoid impossible schedules and deadlocks in project management tools.

💼 Career

Cycle detection is a common problem in software engineering, especially in dependency management, compilers, and workflow systems.

1

Create the directed graph

Create a dictionary called graph with these exact entries: 'A': ['B'], 'B': ['C'], 'C': ['A'], 'D': ['E'], 'E': []

DSA Python

# Your code here

Hint

Use a dictionary where each key is a task and the value is a list of tasks it points to.

2

Create sets to track visited and recursion stack

Create two empty sets called visited and rec_stack to track visited tasks and tasks in the current recursion stack

DSA Python

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

# Your code here

Hint

Use set() to create empty sets for tracking.

3

Implement DFS function to detect cycle

Define a function called dfs that takes a parameter node. Inside, add node to visited and rec_stack. For each neighbor in graph[node], if neighbor is not in visited, recursively call dfs(neighbor) and return true if it returns true. If neighbor is in rec_stack, return true. After checking neighbors, remove node from rec_stack and return false.

DSA Python

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

visited = set()
rec_stack = set()

# Your code here

Hint

Use recursion to explore neighbors and detect back edges indicating cycles.

4

Check all nodes and print if cycle exists

Use a for loop with variable node to iterate over graph. Inside the loop, if node is not in visited, call dfs(node) and if it returns true, print true and break the loop. If no cycle is found, print false after the loop.

DSA Python

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

visited = set()
rec_stack = set()

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

# Your code here

Hint

Check each node and print true immediately if a cycle is detected, otherwise print false.

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