DFS

DFS, or depth-first search, explores one path deeply before returning to try other paths.

DFS can be written recursively or with an explicit stack.

Core Idea

The algorithm visits a vertex, then recursively visits an unvisited neighbor, continuing until it cannot go deeper. Then it returns to earlier vertices and tries remaining neighbors.

This depth-first behavior fits cycle detection, connected components, topological sort, and tree traversal.

Python Example

def dfs(graph, node, visited):
    if node in visited:
        return
 
    visited.add(node)
    print(node)
 
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

The recursive call explores a neighbor before the loop continues to the next neighbor.

Common Confusions

DFS traversal order can depend on neighbor order. Different adjacency list orders can produce different visit sequences while still being correct.

Recursive DFS can hit Python’s recursion limit on large or deep graphs.

When To Use It

Use DFS when the problem needs deep exploration, component discovery, cycle detection, tree-like recursion, or entry/exit timing.