Graph Algorithms

What Is DFS

Depth-first search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a source node, marks it as visited, then recursively visits every unvisited neighbor. When it reaches a node with no unvisited neighbors, it backtracks to the previous node and continues.

DFS produces a traversal order that goes deep before going wide. This makes it useful for exploring all paths, detecting cycles, and solving problems that require exploring the full depth of a structure.

DFS Uses a Stack

The connection between DFS and stacks is direct: the algorithm always processes the most recently discovered node next, which is exactly LIFO behavior. In the recursive version, the call stack acts as the stack. In the iterative version, you use an explicit stack data structure.

When you push a node's neighbors onto the stack, the last neighbor pushed is the first one explored. This is what creates the depth-first behavior: you go as deep as possible down one path before trying another.

Iterative DFS Algorithm

Here is the step-by-step algorithm:

1. Push the starting node onto the stack.
2. While the stack is not empty, pop a node.
3. If the node has not been visited, mark it as visited and process it.
4. Push all unvisited neighbors of this node onto the stack.
5. Repeat from step 2.

Important: you mark nodes as visited when you pop them, not when you push them. This prevents duplicate processing but means the same node may be pushed multiple times. If you mark on push instead, you avoid duplicates but change the traversal order slightly.

DFS on a Graph

Consider this graph:

A -- B -- D
|    |
C -- E -- F

Starting from A, one possible DFS traversal is: A, B, D, E, C, F. The stack trace would be:

Push A
Pop A (visit A), push B, C
Pop C (visit C), push E
Pop E (visit E), push B, F
Pop F (visit F)
Pop B (visit B), push D
Pop D (visit D)
Stack empty. Done.
Traversal: A, C, E, F, B, D

Note that the exact order depends on the order in which neighbors are pushed. Different push orders produce different valid DFS traversals.

DFS on a Binary Tree

DFS on a binary tree has three common orderings based on when you process the node relative to its children:

• Pre-order: Process node, then left subtree, then right subtree.
• In-order: Process left subtree, then node, then right subtree (gives sorted order for BSTs).
• Post-order: Process left subtree, then right subtree, then node (used for deletion and expression evaluation).

For iterative in-order DFS, use a stack and a pointer that moves left until it cannot, then pops and processes, then moves right.

Recursive DFS vs Iterative DFS

DFS Applications

• Cycle detection: If DFS encounters a node that is already in the current recursion stack, a cycle exists in a directed graph.
• Topological sort: DFS-based topological sort processes nodes in reverse finish order. Used for scheduling tasks with dependencies.
• Connected components: Run DFS from each unvisited node in an undirected graph. Each run discovers one connected component.
• Path finding: DFS can find if a path exists between two nodes. It finds one valid path but not necessarily the shortest.
• Maze solving: DFS explores all possible paths in a maze until it finds the exit.
• Strongly connected components: Kosaraju's and Tarjan's algorithms use DFS to find SCCs in directed graphs.

Code Examples

Python

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

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['B', 'C', 'F'],
    'F': ['E']
}
print(dfs_iterative(graph, 'A'))

JavaScript

function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    const order = [];
    while (stack.length > 0) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            order.push(node);
            for (const neighbor of graph[node]) {
                if (!visited.has(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
    return order;
}

const graph = {
    A: ['B', 'C'],
    B: ['A', 'D', 'E'],
    C: ['A', 'E'],
    D: ['B'],
    E: ['B', 'C', 'F'],
    F: ['E']
};
console.log(dfsIterative(graph, 'A'));

Time and Space Complexity

Time: O(V + E) where V is the number of vertices and E is the number of edges. Each vertex is processed once and each edge is examined once.

Space: O(V) for the visited set and the stack. In the worst case (a line graph), the stack holds all V vertices. For balanced trees, the stack depth is O(log V).

Compare this to BFS which also runs in O(V + E) time but always uses O(V) space for the queue regardless of graph structure. DFS can be more space-efficient on graphs that are deep but narrow.