Cycle Detection with BFS/DFS

Introduction

In our previous lessons, you've mastered the mechanics of Breadth-First Search (BFS) and Depth-First Search (DFS). We've seen how they traverse graphs in fundamentally different ways—BFS exploring level-by-level, and DFS plumbing the depths of each path.

Today, we'll leverage that knowledge for a crucial application: detecting cycles. This lesson directly addresses the learning outcome: Apply BFS or DFS to detect cycles in both directed and undirected graphs.

Cycle detection is a classic problem with practical implications. For instance, in software engineering, it can be used to find circular dependencies in build systems or modules. In operating systems, it's used to detect deadlocks where processes are stuck waiting for each other in a circular chain.

We will break this down into two main parts:

1. Detecting cycles in undirected graphs.
2. Detecting cycles in directed graphs.

For each part, we'll see how to adapt both DFS and BFS for the task and understand the subtle but important differences in the required logic.

1. Cycle Detection in Undirected Graphs

In an undirected graph, an edge between u and v is a two-way street. This introduces a small challenge: if we traverse from u to v, the traversal algorithm will immediately see u as a visited neighbor of v. We need to distinguish this immediate backtracking from a "true" cycle.

The key insight for undirected graphs is to keep track of the node we just came from—the parent node in the traversal tree. A cycle is detected not when we find any visited node, but when we find a visited node that is not our immediate parent.

Using Depth-First Search (DFS)

The recursive nature of DFS makes it very natural to pass the parent node down through the recursive calls.

The logic is as follows:

• When performing DFS(currentNode, parentNode):
• For each neighbor of currentNode:
  • If the neighbor has not been visited, we continue the traversal with a recursive call: DFS(neighbor, currentNode).
  • If the neighbor has been visited and it is not the parentNode, we have found a back edge that completes a cycle.

The following video provides an excellent step-by-step walkthrough of this exact logic.

Using Breadth-First Search (BFS)

We can apply the same parent-tracking logic to BFS. Since BFS is iterative, instead of passing the parent through function calls, we'll store it in the queue alongside the node.

The logic is:

1. Use a queue that stores pairs of (node, parent).
2. When starting the traversal from a source node s, push (s, -1) into the queue (using -1 or another special value to indicate no parent).
3. When you dequeue a pair (currentNode, parentNode):
4. For each neighbor of currentNode:
   • If the neighbor has not been visited, mark it as visited and enqueue (neighbor, currentNode).
   • If the neighbor has been visited and is not the parentNode, a cycle exists.

This video demonstrates the BFS approach.

For undirected graphs, both BFS and DFS with parent tracking are effective and have a time complexity of $O(|V|+|E|)$.

2. Cycle Detection in Directed Graphs

The parent-tracking trick does not work for directed graphs. In a directed graph, an edge u -> v does not imply an edge v -> u. Finding a path to an already visited node w could mean we've found a cycle, or it could simply mean we've reached a node that was part of a different, already completed traversal branch.

To solve this, we need to know not only if a node has been visited, but also if it's currently part of the active recursion path. We use a three-state system for this, often called node coloring:

• WHITE: The node has not been visited yet.
• GRAY: The node is currently being visited. It's on the current recursion stack.
• BLACK: The node and all its descendants have been fully visited.

A cycle is detected when our DFS traversal encounters a GRAY node. This indicates a back edge—an edge pointing from a node to one of its ancestors in the DFS tree, which closes a loop.

Using Depth-First Search (with Coloring)

This is the most common and robust method for detecting cycles in a directed graph.

The algorithm works like this:

1. Initialize two sets, visiting (for GRAY nodes) and visited (for BLACK nodes).
2. Start a DFS from each unvisited node in the graph.
3. In the DFS(currentNode) function:
   a. Move currentNode from WHITE to GRAY state (add it to visiting).
   b. For each neighbor of currentNode:
   i. If neighbor is in the visiting (GRAY) set, you have found a back edge. A cycle exists!
   ii. If neighbor is not in the visited (BLACK) set, recursively call DFS(neighbor). If that recursive call returns true (indicating a cycle was found downstream), propagate true up.
   c. Move currentNode from GRAY to BLACK state (remove it from visiting and add it to visited). This happens after exploring all its neighbors.
   d. Return false (no cycle found from this path).

The following resource explains this concept of back edges and node coloring.

Using Breadth-First Search (via In-Degrees)

Detecting a cycle with BFS in a directed graph is less direct and is intrinsically linked to the concept of topological sorting, which we will explore more in Module 9.

The core idea is that a directed graph has a cycle if and only if it's impossible to create a complete topological sort. We can detect this using a BFS-based approach known as Kahn's algorithm.

Here's the intuition and process:

1. A node with an in-degree of 0 can safely be placed first in a sorted order because no other nodes point to it.
2. Once we "process" this node, we can imagine removing it and its outgoing edges from the graph. This may cause some of its neighbors' in-degrees to drop to 0.
3. These new in-degree-0 nodes can be processed next.
4. We continue this process until no more nodes can be processed.

If, at the end, the number of nodes we processed is less than the total number of nodes in the graph, it means some nodes were left over. These leftover nodes must be part of a cycle, as they are all waiting for each other, and none could reach an in-degree of 0.

The algorithm:

1. Compute In-Degrees: Calculate the in-degree for every vertex in the graph.
2. Initialize Queue: Create a queue and add all vertices with an in-degree of 0.
3. Process Nodes:
   • Initialize a count of visited nodes to 0.
   • While the queue is not empty:
     • Dequeue a vertex u.
     • Increment count.
     • For each neighbor v of u:
       • Decrement the in-degree of v.
       • If the in-degree of v becomes 0, enqueue v.
4. Check for Cycle: After the loop finishes, if count < totalNumberOfVertices, the graph contains a cycle. Otherwise, it is a Directed Acyclic Graph (DAG).

This BFS-based approach also runs in $O(|V|+|E|)$ time.

Conclusion

You have now learned how to adapt both BFS and DFS to solve the important problem of cycle detection, appreciating the different strategies required for undirected and directed graphs.

Key Takeaways:

• Undirected Graphs: A cycle is found when a traversal encounters a visited node that is not its immediate parent. This logic works for both BFS and DFS.
• Directed Graphs (DFS): Use a three-state system (e.g., WHITE, GRAY, BLACK). A cycle is detected when DFS finds a back edge to a GRAY node (one currently in the recursion stack).
• Directed Graphs (BFS): Use an approach based on in-degrees (Kahn's algorithm). A cycle exists if not all nodes can be processed by repeatedly removing nodes with an in-degree of 0.
• All these methods maintain the efficient $O(|V|+|E|)$ time complexity of the underlying traversal algorithms.

Preview of the Next Lesson:

With our exploration of fundamental graph traversal and its applications complete, we will move on to a new class of graph problems. In the next module, we'll start with algorithms for finding the shortest path in weighted graphs. Our first lesson will be on Dijkstra's algorithm, a famous and widely used greedy algorithm for finding the single-source shortest paths in a graph with non-negative edge weights.