Graph Traversal Patterns: BFS vs DFS with Cycle Detection in Directed and Undirected Graphs

Introduction

Graph traversal is a foundational concept in computer science and software engineering. Whether you are building social network recommendation engines, routing packets across networks, or resolving complex module dependencies in a bundler, graphs are the underlying data structure.

Mastering graph algorithms requires a deep understanding of two fundamental traversal strategies: Breadth-First Search (BFS) and Depth-First Search (DFS). In this technical deep-dive, we will explore adjacency list representations, examine how to traverse directed and undirected graphs, implement robust cycle detection strategies (including the 3-color White-Gray-Black algorithm), and use BFS to solve unweighted shortest path problems.

1. Graph Representation: The Adjacency List

Before traversing a graph, we must decide how to store it in memory. For sparse graphs, which are common in real-world applications, the adjacency list is the preferred representation due to its $O(V + E)$ space complexity (where $V$ is the number of vertices and $E$ is the number of edges).

Below is an idiomatic implementation of an unweighted graph using an adjacency list in Python:

from typing import Dict, List

class Graph:
    def __init__(self, directed: bool = False):
        self.adj_list: Dict[int, List[int]] = {}
        self.directed = directed

    def add_vertex(self, vertex: int) -> None:
        if vertex not in self.adj_list:
            self.adj_list[vertex] = []

    def add_edge(self, u: int, v: int) -> None:
        self.add_vertex(u)
        self.add_vertex(v)
        self.adj_list[u].append(v)
        if not self.directed:
            self.adj_list[v].append(u)

2. Depth-First Search (DFS) and Cycle Detection

Core Mechanics

DFS explores as deep as possible along each branch before backtracking. It relies heavily on a stack (either the system call stack via recursion or an explicit stack data structure) and a visited set to prevent infinite loops.

Cycle Detection in Undirected Graphs

In an undirected graph, a cycle exists if we encounter a visited vertex that is not the immediate parent of the current vertex.

def has_cycle_undirected(graph: Dict[int, List[int]]) -> bool:
    visited = set()

    def dfs(node: int, parent: int) -> bool:
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex, -1):
                return True
    return False

Cycle Detection in Directed Graphs (The 3-Color Algorithm)

Undirected cycle detection fails in directed graphs because encountering a previously visited node does not automatically mean a cycle exists; it could be a diamond dependency.

To accurately detect cycles in directed graphs, we use the 3-Color Algorithm (White-Gray-Black):

1. White (0): Unvisited node.
2. Gray (1): Currently visiting node (in the current recursion stack).
3. Black (2): Fully processed node (all descendants explored).

A cycle is detected if and only if we encounter a Gray node during traversal.

def has_cycle_directed(graph: Dict[int, List[int]]) -> bool:
    # 0: White, 1: Gray, 2: Black
    colors = {node: 0 for node in graph}

    def dfs(node: int) -> bool:
        colors[node] = 1  # Mark as Gray

        for neighbor in graph[node]:
            if colors[neighbor] == 1: # Back-edge found
                return True
            if colors[neighbor] == 0:
                if dfs(neighbor):
                    return True

        colors[node] = 2  # Mark as Black
        return False

    for vertex in graph:
        if colors[vertex] == 0:
            if dfs(vertex):
                return True
    return False

3. Breadth-First Search (BFS) and Shortest Paths

Core Mechanics

BFS explores the graph level by level, visiting all neighbors of a node before moving to the next level. It utilizes a Queue (FIFO) data structure, typically implemented via collections.deque in Python for $O(1)$ pops from the left.

Shortest Path in Unweighted Graphs

Because BFS explores nodes in increasing order of their distance from the source, the first time we reach a target node, we are guaranteed to have found the shortest path in terms of edge count.

from collections import deque

def shortest_path_bfs(graph: Dict[int, List[int]], start: int, target: int) -> List[int]:
    if start == target:
        return [start]

    queue = deque([start])
    visited = {start}
    parent = {start: None}

    found = False
    while queue:
        current = queue.popleft()

        if current == target:
            found = True
            break

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = current
                queue.append(neighbor)

    if not found:
        return []

    # Reconstruct path
    path = []
    curr = target
    while curr is not None:
        path.append(curr)
        curr = parent[curr]

    return path[::-1]

4. Comparing BFS and DFS

Feature	Breadth-First Search (BFS)	Depth-First Search (DFS)
Data Structure	Queue (FIFO)	Stack (LIFO / Recursion)
Time Complexity	$O(V + E)$	$O(V + E)$
Space Complexity	$O(W)$ (where $W$ is max width)	$O(H)$ (where $H$ is max height/depth)
Shortest Path	Guaranteed (unweighted graphs)	Not guaranteed
Primary Use Cases	Shortest path, level-order traversal	Topological sort, cycle detection, maze solving

Conclusion

Understanding graph traversal patterns is non-negotiable for systems design and algorithmic problem-solving. By utilizing adjacency lists for memory efficiency, applying the 3-color algorithm for directed cycle detection, and leveraging BFS queues for shortest path discovery, you can reliably tackle complex graph problems in production and technical interviews alike.