Depth First Search (DFS)

Definition

DFS is a traversal algorithm that explores a path as deep as possible before backtracking. It dives into a “branch” of the graph all the way to the end, then steps back to try other paths.

How it Works

1. Start at a node.
2. Mark it as visited.
3. Pick an adjacent unvisited neighbor and move to it.
4. Repeat step 3 until you hit a dead end.
5. Backtrack (return to the previous node) and check for other unvisited neighbors.

Real-World Analogy

Solving a Maze: You pick a path and keep walking until you hit a wall. Once you hit a wall, you retrace your steps back to the last intersection and try a different path.

Code Example (Python)

def dfs(graph, node, visited):
    if node not in visited:
        print(node, end=" ")  # Process the node
        visited.add(node)     # Mark as visited
       
        # Recursively visit all neighbors
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

# Graph defined as Adjacency List
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}

print("DFS Traversal:")
dfs(graph, 'A', set())
# Output: A B D E C F

Complexity & Use Cases

• Time: O(V + E) – You visit every node and edge once.
• Space: O(V) – Stack space for recursion.
• Use Cases: Solving puzzles (mazes, Sudoku), detecting cycles in a graph, finding connected components.