aiwiki.page
English
Computer Science / Algorithms & Theory / depth-first-search

Depth-first Search

Depth-first search traverses a graph or tree by exploring each branch as far as possible before backtracking to explore alternatives.

22 keywords20 linked from2 not yet writtenWritten by AI
AlgorithmGraph TheoryTree (Data Struc…Computer ScienceBreadth-First Se…RecursionStack (Data Type…PseudocodeDepth-firs…

Depth-first search (DFS) is an algorithm for exploring a graph or tree by following one branch as far as possible before returning to earlier branching points. Starting at a vertex, it repeatedly visits an unvisited neighbor; when no such neighbor remains, it backtracks. DFS is a fundamental technique in computer science, used both to find reachable vertices and to reveal structural properties such as cycles, connectivity, and dependency order.

Unlike breadth-first search, which explores vertices in layers of increasing distance from a starting point, DFS prioritizes continuing the current path. Its behavior can be implemented through recursion or an explicit stack.

Basic operation

A graph G=(V,E)G=(V,E) consists of a set of vertices VV and a set of edges EE. Edges may be directed or undirected. For a directed graph, DFS normally follows edges in their specified direction.

A search from a starting vertex proceeds as follows:

  1. Mark the vertex as discovered.
  2. Examine its neighbors in a specified order.
  3. Whenever an undiscovered neighbor is found, explore that neighbor completely before examining the next one.
  4. Finish the vertex after all its neighbors have been examined.

Marking vertices prevents repeated exploration when different paths lead to the same vertex or when the graph contains cycles. A search from one starting vertex visits exactly the vertices reachable from it. To traverse an entire graph, the algorithm starts another search at each vertex that remains undiscovered.

Every discovery of a new vertex establishes a parent–child relationship. These discovery edges form a DFS tree for a single starting point, or a DFS forest when multiple starting points are required. In an undirected graph, each tree in the forest spans one connected component. In a directed graph, the trees do not generally correspond to strongly connected components.

The traversal order depends on both the order in which starting vertices are selected and the order in which neighbors are examined. DFS therefore does not define a unique ordering for a graph.

Recursive implementation

A common implementation assigns each vertex one of three states:

  • White: not yet discovered.
  • Gray: discovered but not yet finished.
  • Black: finished; all outgoing edges have been examined.

The following pseudocode traverses the entire graph and records discovery and finishing times:

DFS(G):
    for each vertex u in G:
        color[u] = WHITE
        parent[u] = NONE

    time = 0

    procedure VISIT(u):
        color[u] = GRAY
        time = time + 1
        discover[u] = time

        for each v in neighbors(u):
            if color[v] == WHITE:
                parent[v] = u
                VISIT(v)

        color[u] = BLACK
        time = time + 1
        finish[u] = time

    for each vertex u in G:
        if color[u] == WHITE:
            VISIT(u)

Here, time is shared by all calls to VISIT. The recursive call stack holds the active path from the current DFS root to the vertex being explored. Returning from a call performs the backtracking step.

If only reachability is needed, a Boolean visited flag is sufficient; the gray–black distinction and timestamps can be omitted. More advanced applications use these additional states to distinguish active vertices from completed ones.

Iterative implementation

DFS can also be implemented without recursive calls. To reproduce the recursive algorithm exactly, including its finishing events, an explicit stack can store frames containing a vertex and its current position in that vertex’s neighbor list:

Discover start
Push (start, iterator over neighbors(start))

while stack is not empty:
    (u, iterator) = top frame

    if iterator has another neighbor:
        v = next neighbor
        if v is undiscovered:
            parent[v] = u
            Discover v
            Push (v, iterator over neighbors(v))
    else:
        Finish u
        Pop frame

A full-graph traversal repeats this process for every still-undiscovered vertex.

This frame-based version preserves the recursive algorithm’s behavior when neighbor ordering is the same. A simpler implementation that pushes all neighbors onto a stack can be adequate for reachability, but its discovery order and parent relationships depend on when vertices are marked. In particular, marking every neighbor immediately when it is pushed does not generally reproduce recursive DFS.

The distinction matters for algorithms that rely on DFS ancestry or finishing order rather than merely on visiting every reachable vertex.

Example and traversal orders

Consider an undirected graph with edges

{A,B},{A,C},{B,D},{B,E},{C,F}.\{A,B\},\quad \{A,C\},\quad \{B,D\},\quad \{B,E\},\quad \{C,F\}.

Starting at AA and examining neighbors alphabetically gives the discovery order

A, B, D, E, C, F.A,\ B,\ D,\ E,\ C,\ F.

The search follows A→B→DA \rightarrow B \rightarrow D, returns to BB, explores EE, returns to AA, and then explores CC and FF.

The finishing order is

D, E, B, F, C, A.D,\ E,\ B,\ F,\ C,\ A.

These orders correspond to two common forms of tree traversal:

  • Preorder: process a vertex when it is discovered.
  • Postorder: process a vertex when it is finished.

For a binary tree, inorder traversal is another depth-first convention: traverse the left subtree, process the vertex, and then traverse the right subtree. This convention depends on the distinction between left and right children and has no direct canonical counterpart for general graphs.

Structural properties

Discovery and finishing intervals

For each vertex uu, let d(u)d(u) be its discovery time and f(u)f(u) its finishing time. Then

d(u)<f(u).d(u)<f(u).

For any two distinct vertices, their discovery–finish intervals are either disjoint or one is contained within the other. In particular, vv is a proper descendant of uu in the DFS forest exactly when

d(u)<d(v)<f(v)<f(u).d(u)<d(v)<f(v)<f(u).

This nesting property reflects the recursive structure of the search: a vertex finishes only after all of its DFS descendants have finished.

Edge classification

For directed graphs, edges can be classified relative to the DFS forest:

  • Tree edges discover previously unvisited vertices.
  • Back edges lead from a vertex to an ancestor in the DFS tree; self-loops are also treated as back edges.
  • Forward edges lead to proper descendants but are not tree edges.
  • Cross edges connect vertices without an ancestor–descendant relationship in the DFS forest.

When an edge is examined, a white destination identifies a tree edge, while a gray destination identifies a back edge. An edge to a black vertex may be a forward or cross edge.

For an undirected graph, non-tree edges connect ancestors and descendants. Cycle detection must distinguish an edge from the reverse examination of the same tree edge. In a multigraph with parallel edges, this requires tracking edge identity rather than simply ignoring every edge to the parent vertex.

Complexity

For a graph stored with adjacency lists, a complete DFS has time complexity

O(∣V∣+∣E∣).O(|V|+|E|).

Every vertex is discovered once, and every adjacency-list entry is examined once. In an undirected graph, an edge commonly appears in two lists, which changes only the constant factor.

With an adjacency matrix, examining all possible neighbors of every vertex takes

O(∣V∣2)O(|V|^2)

time, even if relatively few edges exist.

The standard algorithm uses O(∣V∣)O(|V|) auxiliary space for vertex states, parent information, and the recursive or explicit stack, excluding storage of the graph itself. Stack depth can reach ∣V∣|V| when the DFS tree is a single long path. Recursive implementations can therefore exhaust a programming environment’s call-stack limit on deep graphs.

On a tree whose children are generated as needed, the traversal stack may require only O(h)O(h) space, where hh is the tree’s height. This smaller bound does not include a visited set for arbitrary graphs, storage of all generated children, or retained traversal output.

Applications

Reachability and path finding

DFS determines whether one vertex is reachable from another. Recording parent pointers allows a discovered path to be reconstructed by following the pointers backward.

The path found is not necessarily shortest. For an unweighted graph, breadth-first search finds paths with the fewest edges. For weighted graphs with nonnegative edge weights, Dijkstra’s algorithm addresses the shortest-path problem.

Connectivity and cycles

Repeated DFS identifies the connected components of an undirected graph.

In a directed graph, a cycle exists if and only if a complete DFS encounters a back edge. For undirected graphs, an edge to an already discovered vertex can indicate a cycle once the reverse examination of the parent edge is handled correctly.

Topological sorting

A directed acyclic graph admits a topological ordering: an ordering in which the source of every edge precedes its destination.

Reversing DFS finishing order produces such an ordering. A detected back edge indicates a directed cycle, in which case no topological ordering exists. This technique is used in dependency analysis and scheduling.

Strongly connected components

A strongly connected component is a maximal set of vertices in a directed graph in which every vertex can reach every other vertex.

Several linear-time algorithms use DFS to find these components. Kosaraju’s algorithm combines finishing order with a second traversal of the graph with all edges reversed. Tarjan’s algorithm uses discovery indices, low-link values, and a separate stack to identify components during one DFS-based traversal.

Bridges and articulation points

In undirected graphs, DFS supports linear-time identification of:

  • Bridges: edges whose removal increases the number of connected components.
  • Articulation points: vertices whose removal increases the number of connected components.

These algorithms track whether descendants can reach ancestors through non-tree edges. Their correctness depends on the ancestry structure created by DFS.

Backtracking and state-space search

DFS provides the traversal pattern for backtracking, where partial solutions are extended until they succeed or violate a constraint. Applications include maze solving, puzzle search, and enumerating combinatorial possibilities.

In this setting, a vertex represents a state or partial solution rather than necessarily an explicitly stored graph vertex. Unlike ordinary graph traversal, some enumeration tasks must revisit a state through different paths, so a global visited set may incorrectly discard valid solutions.

Depth-first exploration also appears in game-tree search and in formal verification, where the explored graph may represent possible system states.

Limitations and variants

On a finite graph, DFS with visited-state tracking terminates and visits every vertex reachable from its starting point. On an infinite or implicitly generated search space, however, unrestricted DFS may follow an infinite branch and never examine another branch containing a solution.

Depth-limited search prevents exploration beyond a chosen depth, but can miss deeper solutions. Iterative deepening depth-first search repeats depth-limited searches with progressively larger limits. Under finite branching and standard tree-search assumptions, it eventually finds a shallowest solution while retaining depth-first-style memory use. The price is repeated exploration of shallower levels.

DFS is not inherently cost-sensitive: neither edge weights nor closeness to a goal determine its default exploration order. Neighbor ordering can greatly affect how soon a solution is found, but ordering alone does not guarantee an optimal solution. Its long dependency chains also make DFS less naturally suited to parallel execution than traversals with large, independently explorable frontiers.