↑↓ move · ↵ open · esc close

← All algorithms/Finding a path

Depth-first search

Is there any route at all?

Follows one route as deep as it can before backing up. It finds a path quickly, but not necessarily a short one.

TimeO(V + E)
MemoryO(V)
Where it is usedPathfinding →
The idea

Depth-first search is breadth-first search with the queue swapped for a stack: it always continues from the newest cell. It runs down one corridor until it meets a wall or a visited cell, then backs up to the last junction and tries the next branch.

That makes it cheap and good at answering whether the goal can be reached, and it is the basis of many other algorithms: generating mazes, ordering tasks, finding connected regions. As a path finder its weakness is that the first path it finds can wander across the whole map.

Try it

Loading the demo…

The grid with depth-first search selected. On open ground the path it returns snakes around, rarely close to the shortest.

Step by step
  1. 01Push the start on a stack and mark it visited.
  2. 02Pop the newest cell.
  3. 03If it is the goal, follow the stored parents back to the start.
  4. 04Otherwise push each unvisited neighbour, recording where it came from.
  5. 05Repeat until the stack is empty.
In pseudocode
function dfs(start, goal):
    stack  = [start]
    parent = {start: none}
    while stack is not empty:
        cell = stack.pop()                 # the newest cell
        if cell == goal: return path_from(parent, goal)
        for n in neighbours(cell):
            if n not in parent:
                parent[n] = cell
                stack.push(n)
    return no_path
What it costs
Time: O(V + E)Memory: O(V)

The same as breadth-first search in the worst case. On a tree, or with recursion, memory is only the depth of the current route.

Strengths
  • A few lines, and little memory on trees.
  • Answers “is the goal reachable?” quickly.
  • Building block for many other algorithms.
Limits
  • The path found can be far from the shortest.
  • The result depends on the order neighbours are visited.
  • Ignores costs and the goal’s position.
Where it is used
  • 01PathfindingRun it on an empty grid and compare its path length to the other four with “Compare all”.
Related algorithms

Breadth-first search

Finding a path →

Dijkstra’s algorithm

Finding a path →