Depth-First Search

In Turkish: Derinlik Öncelikli Arama

Updated September 30, 20263 min read

In short

Depth-first search is a graph traversal algorithm that follows one path as far as it can go before backtracking to explore the next unvisited branch.

What is depth-first search?

Depth-first search (DFS) is an algorithm for exploring a graph or tree by going deep before going wide. From the starting node, it moves to an unvisited neighbor, then to that node's unvisited neighbor, and keeps going until it reaches a dead end. Then it backtracks to the most recent node that still has unexplored neighbors and continues from there.

DFS is usually written with recursion, where the call stack remembers the way back, or with an explicit stack data structure. It marks each node as visited so that cycles can't send it around in circles forever. With an adjacency list, DFS processes every reachable vertex and edge once, so it runs in O(V + E) time; a recursive DFS needs O(V) extra memory in the worst case for the visited set and the call stack, and on a tree, which needs no visited set, the stack only grows as deep as the tree's height.

Exploring a maze while marking your trail with chalk is a good picture: you follow one corridor to its end, then walk back to the last junction and try a turn you haven't marked yet. DFS is the basis for detecting cycles, topological sorting (ordering tasks so each one comes after its dependencies, as build tools and package managers do), finding connected components, and solving puzzles such as mazes and sudoku by backtracking. The preorder, inorder, and postorder tree traversals are all forms of DFS.

DFS is most often contrasted with breadth-first search (BFS). BFS uses a queue to explore the nearest nodes first and finds shortest paths by edge count, while DFS dives deep and does not guarantee the shortest path. A practical pitfall is recursion depth: on very deep graphs, a recursive DFS can hit the language's recursion limit or cause a stack overflow, so an iterative version with an explicit stack is safer.

Key takeaways

DFS follows one path as deep as possible, then backtracks.
It uses recursion or an explicit stack, plus a visited set to handle cycles.
It runs in O(V + E) time with an adjacency list.
DFS is the basis for cycle detection, topological sorting, and backtracking puzzles.
Unlike BFS, DFS does not guarantee the shortest path.

Example

Iterative depth-first search with an explicit stackpython

def dfs(graph, start):
    visited, order = set(), []
    stack = [start]  # last in, first out: the newest path is explored first
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        # Push neighbors in reverse so the first neighbor is explored first
        stack.extend(reversed(graph[node]))
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": ["A"]}  # E -> A is a cycle
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E']

Readers ask

What is the difference between DFS and BFS?

DFS goes as deep as possible along one path before backtracking, using a stack or recursion. BFS explores all nodes at the current distance before going farther, using a queue, which is why BFS finds shortest paths by edge count and DFS does not.

Is DFS recursive?

It is often written recursively, because the call stack naturally remembers the way back. It can also be written with an explicit stack, which avoids recursion limits and stack overflows on very deep graphs.

What is DFS used for?

Common uses include detecting cycles, topological sorting of dependencies, finding connected components, exploring every possible path, and backtracking algorithms for puzzles such as mazes and sudoku.

Often compared

BFS vs DFSBFS explores a graph level by level with a queue, finding shortest paths in unweighted graphs, while DFS goes deep down one branch, then backtracks.