Depth-First Search (DFS)

#How does it work?

Depth-first search (DFS) follows one branch of a graph as deep as it can; at a dead end it goes back to the last place it branched off (backtracking) and tries another branch from there.

A stack gives this behaviour: DFS is usually written recursively, in which case the stack is the call stack itself. At any moment the nodes on the stack form the path from the start to the current node.

DFS finds a path between two nodes but doesn't guarantee the shortest one. In return it is great for structural questions such as finding cycles, topological sorting and connected components.

#Try it yourself

#Step by step

1. 01Visit the start node and push it on the stack.
2. 02Move to the first unvisited neighbour and repeat there.
3. 03When no unvisited neighbour is left, pop the node and go back to the previous one (backtrack).
4. 04To find a path: when the target is reached, the stack is the path from the start to the target.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

# Undirected graph as adjacency lists (neighbours in increasing order).
EDGES = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]
graph = {v: [] for v in range(1, 8)}
for a, b in EDGES:
    graph[a].append(b)
    graph[b].append(a)
for v in graph:
    graph[v].sort()


def dfs(u: int, visited: set, order: list) -> list:
    visited.add(u)
    order.append(u)
    for v in graph[u]:
        if v not in visited:
            dfs(v, visited, order)  # go deep first; returning = backtracking
    return order


def find_path(u: int, target: int, visited: set, path: list) -> bool:
    visited.add(u)
    path.append(u)
    if u == target:
        return True
    for v in graph[u]:
        if v not in visited and find_path(v, target, visited, path):
            return True
    path.pop()  # dead end
    return False


print(" ".join(map(str, dfs(1, set(), []))))
path = []
find_path(1, 6, set(), path)
print(" ".join(map(str, path)))  # a path, but not the shortest (1 3 6)

#Complexity

Each node is visited once and each edge is looked at once from each end. Recursive DFS can overflow the call stack on very deep graphs (e.g. a chain of a million nodes); then it has to be written iteratively with an explicit stack.

#When to use it?

Generating and solving mazes, puzzle and backtracking problems (Sudoku, N-queens), cycle detection, topological sorting (build and task dependencies), connected and strongly connected components, bridges and articulation points are all solved with DFS.

#Practice

Log in to answer questions and save your progress.