DFS: Traversal and Cycle Detection

The Five Concepts for Today

We will break down DFS into five interconnected concepts, building from the core idea to advanced, interview-critical applications:

1. The Core Idea of DFS: The philosophy of "go deep."
2. Recursive DFS: The elegant implementation using the call stack.
3. Iterative DFS: The robust, production-safe implementation with an explicit stack.
4. Application 1: Cycle Detection in Undirected Graphs.
5. Application 2: Cycle Detection in Directed Graphs (The 3-Color Method).

Concept 1: The Core Idea of DFS

Technical Explanation

Depth-First Search (DFS) is a graph traversal algorithm that starts at a source node and explores as far as possible along each branch before backtracking. Unlike BFS which uses a First-In, First-Out (FIFO) queue, DFS uses a Last-In, First-Out (LIFO) strategy, which is naturally implemented with a stack.

The algorithm's philosophy is:

1. Visit a node.
2. Pick one of its unvisited neighbors and immediately go to it.
3. Repeat this process, diving deeper and deeper into the graph.
4. Once you hit a "dead end" (a node with no unvisited neighbors), you backtrack to the previous node and try another one of its unvisited neighbors.

This process continues until all reachable nodes have been visited. The path it takes is often long and winding, in stark contrast to the systematic layers of BFS.

Metaphor: Solving a Maze

Imagine you're solving a maze using the "right-hand rule": you keep your right hand on a wall and just keep walking.

• You will follow one corridor as far as it goes (diving deep).
• When you hit a dead end, you turn around and retrace your steps until you find an unexplored fork in the path (backtracking).
• You then take that new path, again following it to its conclusion.

This is exactly how DFS explores a graph. The stack acts as your memory of which forks you have yet to try.

Python Code: Basic Traversal Order

This simple snippet demonstrates the path DFS takes. We'll use recursion here for simplicity, which we will formalize in the next concept.

def dfs_traversal_simple(graph, node, visited=None):
    """
    Performs a simple DFS traversal to show the order of visited nodes.
    """
    if visited is None:
        visited = set()
    
    if node not in visited:
        print(node, end=" ") # Process the node
        visited.add(node)
        for neighbor in graph.get(node, []):
            dfs_traversal_simple(graph, neighbor, visited)

# Example graph from previous lesson
graph_example = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

print("DFS Traversal Order (can vary based on neighbor order):")
dfs_traversal_simple(graph_example, 'A')
# Expected Output could be: A B D E F C 
# Note how it goes A->B->D (deep) before ever visiting C.

Concept 2: Recursive DFS Implementation

Technical Explanation

The most intuitive way to implement DFS is using recursion. The function call stack itself acts as the LIFO stack we need.

The logic is beautifully simple:

1. Define a function dfs(node, visited).
2. The base case: If node is already in the visited set, return.
3. Mark the current node as visited.
4. Process the node (e.g., add it to a results list).
5. For each neighbor of node, make a recursive call: dfs(neighbor, visited).

The call stack handles the backtracking automatically. When a recursive call for a path finishes (hits a dead end), the program execution returns to the previous function call in the stack, which can then proceed to its next neighbor.

Metaphor: A Chain of Command

Imagine a general (start_node) giving an order.

• The general tells a colonel (neighbor 1): "Scout this region."
• The colonel tells a captain (neighbor 1.1): "Scout this sector."
• This continues down to a private who scouts a single point and reports back.
• Once the captain has received reports from all their soldiers, they report back to the colonel.
• Once the colonel has reports from all their captains, they report back to the general.

The chain of command is the call stack. A report going back up the chain is a function return.

Python Code: Recursive Implementation

This is a more structured implementation, commonly seen in interviews.

def dfs_recursive(graph: dict, start_node: str):
    """
    Performs a DFS traversal using recursion.

    Returns:
        A list of nodes in one possible DFS traversal order.
    """
    visited = set()
    path = []

    def _dfs(node):
        if node in visited:
            return
        
        visited.add(node)
        path.append(node) # Process node
        
        # Explore neighbors
        for neighbor in graph.get(node, []):
            _dfs(neighbor)

    _dfs(start_node)
    return path

# Using the same graph
path_rec = dfs_recursive(graph_example, 'A')
print(f"\nRecursive DFS Path: {path_rec}")

Concept 3: Iterative DFS Implementation

Technical Explanation

While elegant, recursion has a major flaw: it can cause a stack overflow error if the graph is too deep (e.g., a long chain of nodes). Every function call consumes memory on the call stack, which has a limited size. For production systems at companies like Google or Meta, where input sizes can be massive, relying on recursion is a risk.

The solution is an iterative implementation using an explicit stack data structure.

The logic:

1. Initialize a stack with the start_node.
2. Initialize a visited set.
3. Loop while the stack is not empty:
   a. Pop a node from the stack.
   b. If node has been visited, continue.
   c. Mark node as visited and process it.
   d. For each neighbor of node, push it onto the stack.

This achieves the same LIFO behavior without deep recursion, making it robust and scalable.

Python Code: Iterative Implementation

Notice we often add neighbors to the stack in reverse order to match the traversal order of the typical recursive implementation. This is a common interview trick.

def dfs_iterative(graph: dict, start_node: str):
    """
    Performs a DFS traversal using an explicit stack.

    Returns:
        A list of nodes in one possible DFS traversal order.
    """
    stack = [start_node]
    visited = set()
    path = []

    while stack:
        node = stack.pop()

        if node in visited:
            continue
        
        visited.add(node)
        path.append(node)

        # Add neighbors to the stack. Adding them in reverse order of the adjacency
        # list ensures that the first neighbor is processed first, mimicking recursion.
        for neighbor in reversed(graph.get(node, [])):
            if neighbor not in visited:
                stack.append(neighbor)
    
    return path

path_iter = dfs_iterative(graph_example, 'A')
print(f"Iterative DFS Path: {path_iter}")
# With the reversed loop, this should produce the same order as the recursive one.

Concept 4: Application 1: Cycle Detection in an Undirected Graph

Technical Explanation

A primary use of DFS is detecting cycles. In an undirected graph, a cycle exists if, during traversal, we encounter a visited node that is not the immediate parent of the current node.

Why the "not the parent" condition? In an undirected graph, the edge (A, B) means we can go A -> B and B -> A. If we just checked for any visited neighbor, we'd immediately find A when exploring from B, incorrectly flagging a cycle.

The algorithm is a small modification to our recursive DFS:

1. The dfs function now takes (node, parent).
2. When exploring from current_node, iterate through its neighbors.
3. If a neighbor is already visited and neighbor is not the parent of current_node, we have found a back edge. This indicates a cycle.
4. If a neighbor is not visited, recurse: dfs(neighbor, current_node).

Metaphor: One-Way Memory

You're the maze solver again. You have a very short-term memory: you only remember the single chamber you just came from.

• You enter a new chamber.
• You look at the connecting tunnels. One tunnel leads to a chamber you've already visited.
• If that chamber is the one you just came from, that's fine, you just won't go back.
• But if that chamber is not the one you just came from, it means there's another way to get to it. You've found a loop!

Python Code: Undirected Cycle Detection

def has_cycle_undirected(graph: dict) -> bool:
    """
    Checks for a cycle in an undirected graph using DFS.
    """
    visited = set()

    def _dfs(node, parent):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor == parent:
                continue # Don't go back to the immediate parent
            if neighbor in visited:
                return True # Found a back edge to a visited, non-parent node
            if _dfs(neighbor, node): # Recurse
                return True
        return False

    # Handle disconnected graphs by trying to start a DFS from every node
    for node in graph:
        if node not in visited:
            if _dfs(node, None):
                return True
    
    return False

# Example Graphs
undirected_cyclic = {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}
undirected_acyclic = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}

print(f"Graph 1 has cycle: {has_cycle_undirected(undirected_cyclic)}")   # Expected: True
print(f"Graph 2 has cycle: {has_cycle_undirected(undirected_acyclic)}") # Expected: False

Concept 5: Application 2: Cycle Detection in a Directed Graph

Technical Explanation

Detecting cycles in a directed graph is more complex. The simple parent check doesn't work. Consider A -> B and A -> C -> B. When we are at B, we might see a path from a visited node C, but that doesn't form a cycle. A cycle exists only if we find a path from a node back to one of its own ancestors in the current traversal path.

This requires a three-state system, often called the white-grey-black method:

• WHITE: Node has not been visited at all.
• GREY: Node is currently being visited. It's in our current recursion stack. These are the "ancestors".
• BLACK: Node and all its descendants have been fully explored.

The algorithm:

1. Initialize all nodes to WHITE.
2. Start a DFS from any WHITE node. When you first visit a node, change its color to GREY.
3. For each neighbor:
   • If the neighbor is GREY, you've found a back edge to an ancestor. A cycle exists.
   • If the neighbor is WHITE, recurse on it.
4. After exploring all descendants of a node (i.e., after the recursive calls for all its neighbors have returned), change its color to BLACK.

Python Code: Directed Cycle Detection (3-Color Method)

def has_cycle_directed(graph: dict) -> bool:
    """
    Checks for a cycle in a directed graph using 3-color DFS.
    """
    # 0: white (unvisited), 1: grey (visiting), 2: black (visited)
    colors = {node: 0 for node in graph}

    def _dfs(node):
        colors[node] = 1 # Mark as grey (visiting)

        for neighbor in graph.get(node, []):
            if colors.get(neighbor) == 1: # Neighbor is grey -> cycle detected
                return True
            if colors.get(neighbor) == 0: # Neighbor is white
                if _dfs(neighbor):
                    return True
        
        colors[node] = 2 # Mark as black (finished)
        return False

    for node in graph:
        if colors[node] == 0:
            if _dfs(node):
                return True
    
    return False

# Example Graphs
directed_cyclic = {'A': ['B'], 'B': ['C'], 'C': ['A']}
directed_acyclic = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}

print(f"Directed Graph 1 has cycle: {has_cycle_directed(directed_cyclic)}")   # Expected: True
print(f"Directed Graph 2 has cycle: {has_cycle_directed(directed_acyclic)}") # Expected: False

Conclusion

Today you've mastered Depth-First Search, the powerful counterpart to BFS. You've learned how its "go deep" strategy, powered by a stack, leads to a different kind of exploration.

Key Takeaways:

• DFS explores deeply using a LIFO strategy, implemented with a stack (either the implicit call stack or an explicit one).
• Recursive DFS is elegant and concise but risks stack overflow on deep graphs.
• Iterative DFS is more verbose but robust and production-safe, giving you full control over memory.
• Cycle detection is a key application. In undirected graphs, you look for a visited neighbor that isn't your immediate parent. In directed graphs, you use the more robust white-grey-black three-state method to find back edges to ancestors.
• Time complexity for all variants is $O(V+E)$ and space complexity is $O(V)$, same as BFS.

Preview of the Next Lesson:
The ability to detect cycles in a directed graph is not just an academic exercise. It's the prerequisite for one of the most important graph algorithms: Topological Sort. In our next lesson, we will see how we can use DFS to linearly order the vertices of a Directed Acyclic Graph (DAG), an algorithm with profound applications in task scheduling, dependency resolution (like in compilers and build systems), and data processing pipelines.