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.

DFS is useful when the algorithm needs to fully explore a branch before moving to another branch. It is less about shortest distance and more about structure: reachability, components, recursive relationships, and entry or exit order.

Function Contracts

dfs(graph, node, visited) expects visited to be a set supplied by the caller. It marks every vertex reachable from node.

dfs_iterative(graph, start) expects an adjacency list and prints nodes as they are first visited. Both versions need a visited set to avoid repeated traversal through cycles.

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.

Iterative Version

An explicit stack avoids recursive call depth:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
 
    while stack:
        node = stack.pop()
        if node in visited:
            continue
 
        visited.add(node)
        print(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

The exact visit order may differ from recursive DFS because stack order depends on how neighbors are pushed.

Complexity

With an adjacency list, DFS is O(V + E) when it uses a visited set. Each vertex is visited once, and edges are inspected through adjacency lists.

The space is O(V) for the visited set and recursion stack or explicit stack.

What DFS Is Good At

DFS naturally answers questions such as:

• What can be reached from this vertex?
• Which vertices belong to one component?
• Does a directed path lead back to a currently visiting node?
• What is the postorder of a tree or DAG?

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.

DFS does not guarantee the shortest path in an unweighted graph. It may find a path quickly, but not necessarily the shortest one.

When To Use It

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

Use BFS instead when the problem asks for minimum number of equal-cost steps.

The Main Point

DFS explores deeply before returning. It is useful for structure, reachability, components, and recursive graph reasoning, not for shortest unweighted paths.