Skip to main content

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}
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()
        order.append(vertex)
        for neighbor in reversed(graph.get(vertex, ())):
            if neighbor not in visited:
                visited.add(neighbor)
                parent[neighbor] = vertex
                stack.append(neighbor)
    return order, parent

Marking a vertex when it is pushed prevents duplicate frontier entries. Reversing neighbors only preserves a chosen presentation order; traversal order otherwise depends on adjacency order.

Guarantees​

With an adjacency-list representation, DFS visits the reachable subgraph in O(V+E)O(V+E) time and uses O(V)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.

Source​