Depth-First Search

Depth-first search explores one unfinished branch before backtracking. The implicit or explicit stack records the current search frontier.

def dfs(graph, start):
    visited = {start}
    parent = {start: None}
    order = [start]
    stack = [(start, iter(graph.get(start, ())))]

    while stack:
        vertex, neighbors = stack[-1]
        try:
            neighbor = next(neighbors)
        except StopIteration:
            stack.pop()
            continue
        if neighbor not in visited:
            visited.add(neighbor)
            parent[neighbor] = vertex
            order.append(neighbor)
            stack.append((neighbor, iter(graph.get(neighbor, ()))))
    return order, parent

Each stack frame retains its unfinished neighbor iterator. Only one new neighbor is discovered before descending, exactly as in recursive DFS. Discovery order follows adjacency order; marking on discovery prevents repeated visits.

Open full-size image

Numbers mark discovery order. Here the black tree follows one long branch before returning. Compare with BFS: the same graph can have a different discovery tree, and DFS does not guarantee shortest paths.

Pat Morin, Open Data Structures, Figure 12.5; cropped from the PDF. · CC BY 2.5 CA

Guarantees

With an adjacency-list representation, DFS visits the reachable subgraph in $O(V+E)$ time and uses $O(V)$ visited/stack space in the worst case.

DFS produces a depth-first forest and is a basis for:

• connected components;
• topological ordering in directed acyclic graphs;
• cycle detection with the appropriate state model;
• entry/exit times, low-link algorithms, and backtracking searches.

Cycle detection is not just “a visited neighbor exists”: undirected graphs must exclude the parent edge, while directed graphs distinguish active from finished vertices.

DFS versus shortest paths

DFS can find a path, but not necessarily one with the fewest edges. Use BFS for unweighted shortest paths, or a weighted shortest-path algorithm when edges have costs.

Why a stack of suspended scans matters

The recursive semantics described by Open Data Structures finish a child's exploration before resuming its parent's scan. Merely pushing and marking all neighbors at once can find reachable vertices but assign a non-DFS parent tree. For A: [B, C], B: [C], C: [], premature marking would make both B and C children of A, although DFS must reach C through B.

With the code above, start with frame A; discover B and suspend A. Discover C from B and suspend B. Exhaust C, then B, then resume A, whose remaining neighbor C is already visited. The result is order [A, B, C] and parents A: None, B: A, C: B. The stack always represents the active root-to-current path. Popping a frame is its finish event; topological sorting needs those finish events, not simply reversed discovery order.

Assume a finite, unchanged adjacency mapping with hashable vertices and reusable neighbor lists. Missing keys mean no outgoing edges; a missing start is therefore treated as an isolated vertex. Only the reachable component is returned. A full forest needs an outer loop over all vertices, sharing one visited set.

Every vertex is discovered once and each of its adjacency entries is advanced once; exhausted frames are popped once. This gives termination and $O(V+E)$ work for reachable vertices and edges, assuming expected constant-time hash operations. Input storage also includes any unreachable portion of the graph; returned order/parents use $O(V)$, and the visited set plus active stack use $O(V)$ auxiliary storage. With an adjacency matrix, scanning rows instead costs $O(V^2)$ for a full traversal.

Run these boundary checks after the definitions above:

graph = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "X": []}
order, parent = dfs(graph, "A")
assert order == ["A", "B", "C"]
assert parent == {"A": None, "B": "A", "C": "B"}
assert "X" not in parent
assert dfs({}, "A") == (["A"], {"A": None})

Topological order with cycle rejection

A topological order places the source of every directed edge before its destination. Princeton's directed-graph chapter proves that a graph has such an order exactly when it is acyclic, and that reversed DFS finish order works for a DAG.

Track three states: absent means undiscovered, 1 means active on the stack, and 2 means finished. An edge to an active vertex closes a directed cycle; an edge to a finished vertex does not. The outer loop covers disconnected components. Vertices occurring only as neighbors are discovered during traversal; an isolated vertex must appear as a key. As above, the graph must remain unchanged and adjacency lists must be reusable.

def topological_order(graph):
    state = {}
    finished = []
    for root in graph:
        if root in state:
            continue
        state[root] = 1
        stack = [(root, iter(graph.get(root, ())))]
        while stack:
            vertex, neighbors = stack[-1]
            try:
                neighbor = next(neighbors)
            except StopIteration:
                stack.pop()
                state[vertex] = 2
                finished.append(vertex)
                continue
            if state.get(neighbor) == 1:
                raise ValueError("directed cycle: no topological order")
            if neighbor not in state:
                state[neighbor] = 1
                stack.append((neighbor, iter(graph.get(neighbor, ()))))
    return finished[::-1]


dag = {"s": ["a", "b"], "a": ["b"], "X": []}
order = topological_order(dag)
position = {vertex: i for i, vertex in enumerate(order)}
assert set(order) == {"s", "a", "b", "X"}
assert all(position[u] < position[v] for u in dag for v in dag[u])
assert topological_order({}) == []
for cyclic in ({"a": ["a"]}, {"a": ["b"], "b": ["a"]},
               {"ok": [], "x": ["y"], "y": ["x"]}):
    try:
        topological_order(cyclic)
    except ValueError:
        pass
    else:
        raise AssertionError("a cycle must be rejected")

Without a cycle, each edge points to a vertex that finishes before its source: either the target was already finished or DFS finishes it before resuming the source. Reversing finish order therefore puts every edge’s source before its destination. Time is $O(V+E)$ and auxiliary space is $O(V)$ under the same hash-table assumptions. The result need not be unique; adjacency and root order break ties. Use this order for DAG shortest-path relaxation, rather than discovery order or a partial order from a failed cycle check.

In the USF DFS animation, pause when a branch has no unvisited neighbor. Identify the suspended parent that resumes next. Compare this backtracking order with discovery order before trying the topological-order implementation above.

Source

• Open Data Structures: Graph Traversal

My reading · Opened notes are remembered in this browser.