Depth-First Search

What is Depth-First Search?

Depth-First Search (DFS) is a graph traversal algorithm that explores a graph by going as deep as possible along each branch before backtracking. It uses a stack (LIFO - Last In, First Out) to explore nodes, always processing the most recently discovered node first. DFS is useful for exploring all paths, detecting cycles, and solving problems like maze solving. Note: Edge weights are ignored by DFS - it doesn't use weights in its traversal.

How It Works

DFS explores the graph by going deep before going wide, always exploring the most recently discovered node:

1. Start with the source node, mark it as depth 0, and push it onto the stack
2. Pop a node from the top of the stack
3. If the node hasn't been visited, mark it as visited
4. Push all unvisited neighbors onto the stack
5. Repeat until the stack is empty

Implementation

Here's a Python implementation using a stack:

from typing import Dict, List

def dfs(graph: Dict[str, List[str]], start: str) -> Dict[str, int]:
    """
    Perform Depth-First Search to explore a graph and find depths of nodes.
    
    DFS explores as deep as possible along each branch before backtracking.
    Unlike BFS, DFS does NOT guarantee finding the shortest path - it finds
    a path, but not necessarily the one with minimum edges.
    
    Args:
        graph: Adjacency list representation. Each node maps to a list of neighbors.
        start: Starting node identifier.
    
    Returns:
        Dictionary mapping each node to its depth (edges from start in DFS tree).
        Unreachable nodes will have depth float('inf').
    
    Time Complexity: O(V + E) where V is vertices and E is edges.
    Space Complexity: O(V) for stack and visited set.
    """
    depths: Dict[str, int] = {node: float('inf') for node in graph}
    depths[start] = 0
    stack: List[str] = [start]
    visited: set[str] = set()
    
    while stack:
        current = stack.pop()
        
        if current in visited:
            continue
        
        visited.add(current)
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                depths[neighbor] = depths[current] + 1
                stack.append(neighbor)
    
    return depths

# Example
graph = {'A': ['B', 'C', 'E'], 'B': ['C', 'A'],
         'C': ['D', 'E', 'A', 'B'], 'D': ['C', 'E'], 'E': ['A', 'C', 'D']}
print(dfs(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 1}

Time Complexity

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is examined once. This makes DFS very efficient for graph traversal, though it doesn't guarantee finding the shortest path like BFS does.

Edge Cases: If the graph contains disconnected components, DFS will only explore nodes reachable from the start node. Unreachable nodes will be marked as such in the visualization.

Real-World Applications

• Maze solving: exploring all possible paths through a maze
• Cycle detection: detecting cycles in directed and undirected graphs
• Topological sorting: ordering nodes in a directed acyclic graph
• Path finding: finding any path between two nodes (not necessarily shortest)
• Connected components: finding all nodes reachable from a starting node
• Tree/graph traversal: exploring tree structures and graph hierarchies