Cycle Detection in Directed Graph in DSA Python

Mental Model

We want to find if there is a loop in a directed graph where following edges leads back to a starting point.

Analogy: Imagine a set of one-way roads between cities. A cycle means you can start in one city and drive through some roads to return to the same city without reversing.

A -> B -> C
↑         ↓
└─────────

Dry Run Walkthrough

Input: Graph edges: A->B, B->C, C->A (cycle exists)

Goal: Detect if the graph has a cycle

Step 1: Start DFS from node A, mark A as visiting

Visiting: [A], Visited: []

Why: We begin exploring from A to find cycles

Step 2: From A, move to B, mark B as visiting

Visiting: [A, B], Visited: []

Why: Continue exploring neighbors to find cycle

Step 3: From B, move to C, mark C as visiting

Visiting: [A, B, C], Visited: []

Why: Keep going deeper to check for cycles

Step 4: From C, move to A which is already visiting -> cycle detected

Visiting: [A, B, C], Visited: []

Why: Finding a node already in visiting means a cycle

Result:

Cycle detected because A is revisited while still in visiting state

Annotated Code

DSA Python

class Graph:
    def __init__(self, vertices):
        self.graph = {v: [] for v in vertices}

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def _dfs(self, node, visiting, visited):
        visiting.add(node)  # mark node as visiting
        for neighbor in self.graph[node]:
            if neighbor in visiting:  # cycle found
                return True
            if neighbor not in visited:
                if self._dfs(neighbor, visiting, visited):
                    return True
        visiting.remove(node)  # done exploring node
        visited.add(node)  # mark node as visited
        return False

    def has_cycle(self):
        visiting = set()
        visited = set()
        for node in self.graph:
            if node not in visited:
                if self._dfs(node, visiting, visited):
                    return True
        return False

# Driver code
vertices = ['A', 'B', 'C']
g = Graph(vertices)
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.add_edge('C', 'A')
print("Cycle detected" if g.has_cycle() else "No cycle detected")

visiting.add(node) # mark node as visiting

mark current node as being explored to detect back edges

if neighbor in visiting: # cycle found

detect cycle if neighbor is already in current exploration path

if neighbor not in visited:

explore neighbors not fully processed yet

visiting.remove(node) # done exploring node

remove node from current path after exploring all neighbors

visited.add(node) # mark node as visited

mark node as fully processed to avoid reprocessing

Output

Cycle detected

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V) for recursion stack and sets tracking visiting and visited nodes

vs Alternative: Compared to naive repeated path checking which can be exponential, DFS with visiting set is efficient and linear

Edge Cases

Empty graph

No cycle detected because there are no nodes or edges

DSA Python

for node in self.graph:
            if node not in visited:

Graph with single node and no edges

No cycle detected as no edges exist

DSA Python

for node in self.graph:
            if node not in visited:

Graph with multiple disconnected components, one with cycle

Cycle detected because DFS finds cycle in one component

DSA Python

if self._dfs(node, visiting, visited):

When to Use This Pattern

When you need to check if a directed graph has loops, use DFS with visiting and visited sets to detect back edges indicating cycles.

Common Mistakes

Mistake: Not distinguishing between nodes currently being visited and fully visited nodes
Fix: Use two sets: one for nodes in current DFS path (visiting) and one for nodes fully processed (visited)

Mistake: Marking nodes as visited too early before exploring all neighbors
Fix: Only mark node as visited after all neighbors are explored and no cycle found

Summary

Detects if a directed graph contains a cycle by DFS traversal.

Use when you want to know if following directed edges can loop back to a start node.

The key insight is to track nodes currently in the recursion stack to find back edges indicating cycles.

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