Graph Traversal

What actually happens

Cost model and visited discipline

In Python, prefer collections.deque with popleft() for BFS instead of list.pop(0), which is O(n) per dequeue and can accidentally turn a linear graph walk into O(V²).

Interactive traversal demo

Select BFS or DFS and click Run to see how they explore the graph differently.

Frontier and invariant trace

The same topology can produce different valid orders when neighbor order changes. What remains stable is the algorithmic invariant: FIFO layers for BFS and pending subtrees for DFS.

Iterative DFS

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()
        order.append(vertex)
        # Reverse-push gives earlier neighbors priority.
        for neighbor in reversed(graph.get(vertex, ())):
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return order

import java.util.*;

final class IterativeDfs {
    static List<Integer> traverse(List<List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        Deque<Integer> stack = new ArrayDeque<>();
        List<Integer> order = new ArrayList<>();
        visited[start] = true;
        stack.push(start);

        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            order.add(vertex);
            List<Integer> neighbors = graph.get(vertex);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
        return order;
    }
}

Traverse the whole graph, not one component

A start vertex reaches only its component. The outer loop below creates a traversal forest, counts components, and still visits isolated vertices whose adjacency lists are empty.

def components(adj):
    visited = set()
    groups = []
    for start in range(len(adj)):
        if start in visited:
            continue
        group, stack = [], [start]
        visited.add(start)
        while stack:
            u = stack.pop()
            group.append(u)
            for v in adj[u]:
                if v not in visited:
                    visited.add(v)
                    stack.append(v)
        groups.append(group)
    return groups

import java.util.*;

final class Components {
    static List<List<Integer>> find(List<List<Integer>> adj) {
        boolean[] visited = new boolean[adj.size()];
        List<List<Integer>> groups = new ArrayList<>();

        for (int start = 0; start < adj.size(); start++) {
            if (visited[start]) continue;
            List<Integer> group = new ArrayList<>();
            Deque<Integer> stack = new ArrayDeque<>();
            visited[start] = true;
            stack.push(start);

            while (!stack.isEmpty()) {
                int u = stack.pop();
                group.add(u);
                for (int v : adj.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        stack.push(v);
                    }
                }
            }
            groups.add(group); // includes singleton isolated vertices
        }
        return groups;
    }
}

Why BFS gives minimum hop count

Boundary: BFS minimizes number of edges, not total weight. Equal weights are fine; general non-negative weights require Dijkstra, 0/1 weights admit 0-1 BFS, and negative weights require a different argument.

Complexity depends on representation

For an undirected adjacency list, each logical edge is scanned twice; 2E is still O(E). In Java, recursive DFS over a long chain can throw StackOverflowError; prefer an explicit stack when depth is input-controlled.

Worked trace: one graph, two orders

What each traversal is good at

• BFS layers: store dist[v] when enqueueing to get shortest hop-count from the source; also drives 0-1 BFS with a deque when every edge weight is 0 or 1.
• DFS finishing times: Kosaraju / Tarjan SCC algorithms and topological sorting on DAGs are DFS-shaped.
• Edge classification (directed): tree, back, forward, cross edges, useful for cycle proofs and flow/cut intuition.

Failure modes in real implementations

• Marking too late: marking BFS on dequeue or iterative DFS only on pop permits many duplicate frontier entries on converging graphs.
• Recursion controlled by input: a path graph has DFS depth V; use an explicit stack or enforce a safe bound.
• Mutating while traversing: concurrent edge updates can invalidate iteration; use an immutable snapshot, version, or documented consistency model.
• Unstable output: hash-map neighbor order makes traversal and tests nondeterministic; sort or use ordered adjacency when order is part of the API.
• Memory-heavy state: prefer primitive arrays over boxed sets when vertices are dense integers; reset with visit timestamps when many traversals reuse the same graph.

Exercises

1. Draw a small graph where DFS from s reaches t in fewer recursive calls than BFS layers, yet BFS still reports a strictly smaller hop distance. Explain using the visit-mark timing.
2. What breaks if BFS marks a vertex only when it is dequeued? Give a converging diamond graph and count duplicate queue entries.
3. V = 10⁵ path graph. Recursive DFS depth? Which implementation would you ship, and what does the visit mark still guarantee?

Primary sources

• Cormen et al., Introduction to Algorithms (CLRS): BFS, DFS, edge classification, and the BFS shortest-path lemma.
• Sedgewick & Wayne: undirected/directed DFS applications (cycles, topo, CC).
• Skiena, The Algorithm Design Manual: war stories on BFS for unweighted distance.