# Depth-First Search (DFS)

> Walking a graph down one path as far as it goes, then backing up.

**Field:** Software Development  
**Category:** Algorithms & Data Structures  
**Also known as:** DFS, Depth First Search

## Think of it like

Think of it like a maze. Follow one path to the end, then go back and try the next.

## Definition

Depth-first search walks a graph or tree by going as deep as it can down one path first. When it hits a dead end, it steps back and tries the next branch. It keeps its place with a stack, or by calling itself with recursion. It is good for checking if two nodes connect, finding loops and solving puzzles. It does not promise the shortest path.

## Example

Jack's puzzle solver tries one move after another until it gets stuck. Then it backs up one move and tries the next one.

## Why it matters

Many puzzle solvers and maze games are built on it.

## Common mistake

Using it to find the shortest route. DFS finds a path, not the shortest one; use BFS for that.

## Three principles

- **Deep first.** One path to the end.
- **Back up at dead ends.** Then try the next branch.
- **Stack or recursion.** Keeps its place.

## Related terms

- [Breadth-First Search (BFS)](https://learn.benibix.com/term/development/breadth-first-search)
- [Graph (Data Structure)](https://learn.benibix.com/term/development/graph)
- [Stack (Data Structure)](https://learn.benibix.com/term/development/stack)
- [Recursion](https://learn.benibix.com/term/development/recursion)
- [Backtracking](https://learn.benibix.com/term/development/backtracking)

## Told apart from

- [BFS vs DFS](https://learn.benibix.com/compare/bfs-vs-dfs): Breadth-first search walks a graph one layer at a time and finds the path with the fewest steps. Depth-first search follows one path to its end, then backs up.

---

Source: https://learn.benibix.com/term/development/depth-first-search
Author: Behnia Zarei (a developer in Vienna, Austria, who builds and teaches data, AI and business intelligence at BENIBIX)
Publisher: BENIBIX Learn (https://learn.benibix.com/)
Last updated: 2026-11-19
Licence: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). Quote freely with attribution.
