BFS and DFS, in depth: frontiers, visited sets, shortest paths, edge classification, cycle detection and the bugs that make traversals wrong or slow

One algorithm, two containers

Represent a graph as an adjacency list, a map from each vertex to its neighbors. For V vertices and E edges this takes O(V + E) memory; an adjacency matrix takes O(V squared) and only pays off for dense graphs.

Every traversal keeps three pieces of state. The frontier holds vertices discovered but not yet expanded. The visited set records every vertex ever discovered, so nothing is expanded twice. The parent map records where each vertex was reached from. The loop: take a vertex out of the frontier, and for each neighbor not yet visited, mark it, record its parent and add it to the frontier.

The container decides the algorithm. A first-in, first-out queue expands the oldest vertex first and sweeps outward in rings: BFS. A last-in, first-out stack expands the newest first and dives down one path: DFS. A priority queue ordered by distance gives Dijkstra's shortest paths.

BFS: rings, distances and shortest paths

BFS expands every vertex at distance k before any vertex at distance k + 1. So the first time it discovers a vertex, it has found a path with the fewest edges: distance is parent distance plus one, and parent pointers give a shortest path.

from collections import deque

def bfs(graph, source):
    """Return (dist, parent) for every vertex reachable from source."""
    dist = {source: 0}
    parent = {source: None}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in dist:          # mark when DISCOVERED, not when expanded
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return dist, parent

def path_to(parent, target):
    if target not in parent:
        return None                    # unreachable
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

Two lines matter most. deque.popleft is O(1); a Python list with pop(0) shifts every element and turns O(V + E) into O(V squared). And the vertex is marked when discovered, not when dequeued; marking late lets a vertex be enqueued once per neighbor, so the queue grows toward E entries.

BFS only gives shortest paths when every edge costs the same; with weights you need Dijkstra. When weights are only 0 or 1, 0-1 BFS pushes 0-edge vertices to the front of a deque and 1-edge vertices to the back, keeping the distance order without a heap.

DFS: going deep, and the clock that makes it useful

DFS follows one path as far as it can, then backs up to the most recent vertex with unexplored neighbors. What makes it powerful is a clock: a discovery time when you enter a vertex and a finish time when everything reachable from it is explored. Vertices move through three colors: white (unseen), gray (on the current path) and black (finished).

WHITE, GRAY, BLACK = 0, 1, 2

def dfs_all(graph):
    color = {u: WHITE for u in graph}
    parent, disc, fin = {}, {}, {}
    clock = 0

    def visit(u):
        nonlocal clock
        color[u] = GRAY
        clock += 1; disc[u] = clock
        for v in graph[u]:
            if color[v] == WHITE:
                parent[v] = u
                visit(v)
            # color[v] == GRAY here means a back edge: a cycle in a directed graph
        color[u] = BLACK
        clock += 1; fin[u] = clock

    for u in graph:                    # restart from every unvisited vertex
        if color[u] == WHITE:
            parent[u] = None
            visit(u)
    return parent, disc, fin

The outer loop matters: one source reaches only one component, and forgetting it is how a cycle check silently ignores half the graph. The [discovery, finish] intervals nest: any two are disjoint or one contains the other, and v's lies inside u's exactly when v descends from u in the DFS tree. The classical DFS applications all follow from that.

Worked example: both traversals on one graph

Take an undirected graph with eight vertices and eight edges: A-B, A-C, B-D, B-E, C-F, E-F, E-G and F-H. Adjacency lists are sorted alphabetically so the trace is reproducible. Start both traversals at A.

BFS visits A B C D E F G H with distances 0, 1, 1, 2, 2, 2, 3, 3; the path to H is A, C, F, H. DFS enters A B D E F C H G and finishes D C H F G E B A. BFS finds C at distance 1; DFS reaches it at depth 4 via B, E and F. DFS paths are valid, not short.

Now look at the edge each traversal did not use. In BFS it is E-F, joining two layer-2 vertices, which proves an odd cycle (A-B-E-F-C-A) and so the graph is not bipartite. In DFS it is A-C, reaching ancestor A while A is still gray: a back edge, proving a cycle. Two certificates, each for free.

Edge classification, cycles and topological order

In a directed graph, the color of v classifies edge u to v. White: tree edge. Gray: back edge to an ancestor, and a directed graph has a cycle if and only if DFS finds one. Black: a forward edge (v discovered after u) or a cross edge (v discovered before u). Undirected graphs have only tree and back edges, but the check must skip the edge back to the parent, by edge identity when parallel edges exist, or a real two-edge cycle goes unreported.

Topological order falls out of finish times: in a DAG, an edge u to v means v finishes first, so decreasing finish time is a valid build order. Build tools and package managers do exactly this, and the gray vertices on the stack when a back edge appears are the cycle to print in the 'circular dependency' error.

Low-link values extend the same clock to bridges and articulation points. For connectivity queries over a changing edge set, union-find beats a traversal per query.

Iterative DFS that is actually DFS

Recursive DFS is limited by the call stack. CPython's default recursion limit is 1,000 frames, and JVM thread stacks overflow at depths that depend on frame size. A long dependency chain crashes a recursive traversal in production after it passed every small unit test.

The common fix, pushing all neighbors and marking on pop, is not DFS: no finish times, O(E) stack entries and a different order. The faithful version keeps an iterator per frame, exactly what the call stack did for you.

def dfs_iterative(graph, source):
    order, finish = [source], []
    seen = {source}
    stack = [(source, iter(graph[source]))]
    while stack:
        u, neighbors = stack[-1]
        for v in neighbors:
            if v not in seen:
                seen.add(v)
                order.append(v)                   # discovery
                stack.append((v, iter(graph[v])))
                break                             # descend immediately
        else:
            finish.append(u)                      # all neighbors done
            stack.pop()
    return order, finish

On the worked example this returns the preorder A B D E F C H G and the finish order D C H F G E B A, identical to the recursive trace. Memory is O(depth) frames rather than O(E) entries, and depth is bounded only by heap size. Raising the recursion limit is not a substitute: in CPython it trades a clean RecursionError for a possible hard crash of the interpreter when the native stack runs out.

Choosing between them: memory, answers and variants

Memory usually decides it on big graphs: a social graph reaches millions of vertices within three hops, and a BFS frontier holds them all. Bidirectional BFS searches from both ends until the frontiers meet, exploring roughly 2 times b^(d/2) vertices instead of b^d.

Iterative deepening runs depth-limited DFS with limits 1, 2, 3 and so on: DFS memory, shallowest solution, and since most vertices of a bushy tree sit in the last layer, the repeats cost only a constant factor. It suits puzzle and game-tree search, close kin to backtracking. Multi-source BFS seeds the queue with every source at distance 0 to get each vertex's nearest source in one pass.

Traversal in production systems

Real graphs are often implicit: pages discovered by fetching, grid cells, puzzle states. The visited set becomes the main memory cost; key it by a canonical identifier (normalized URL, coordinates, state hash) or you revisit vertices under different names. A Bloom filter saves space, but its false positives silently skip vertices: fine for a crawler, not for a correctness check.

Budget every traversal over external input with a maximum depth, expansion count and deadline, and report which limit stopped it. Log frontier size; one that only grows signals a bad visited key. Keep neighbor order deterministic so runs are reproducible. Level-synchronous BFS parallelizes well, while DFS is inherently sequential. And Edmonds-Karp is Ford-Fulkerson with BFS choosing each augmenting path, which is what makes it polynomial.

Failure modes and how to recognize them

Both traversals run in O(V + E) time with adjacency lists, as analyzed in Big-O analysis, so when one is slow the cause is almost always one of the rows above rather than the algorithm itself.

What to do next

1. Implement BFS with a deque, marking on discovery, and return both distances and the parent map; test it on a path graph, a star and a disconnected graph.
2. Implement recursive DFS with discovery and finish times, then the iterative version, and assert they produce identical orders on random graphs with sorted adjacency lists.
3. Use finish times to topologically sort a small build graph and make the cycle case print the actual cycle.
4. Run a bipartite check with BFS and verify it rejects the five-cycle from the worked example.
5. Take a traversal in your own codebase and add depth, expansion and time budgets plus a frontier-size metric.
6. Replace one weighted-graph BFS you find in code review with Dijkstra, or with 0-1 BFS if the weights are only 0 and 1.