Depth-First Search

noun

say it: “DEPTH FURST SURCH” /dɛpθ fɜrst sɜrtʃ/

A way of exploring a graph by going as far as possible along one path before backing up to try another.

What is depth-first search?

Depth-first search (DFS) explores a graph by following one path as deep as it can, then backing up to the last fork with an untried way, like exploring a maze with a piece of string. Recursion or a stack remembers the forks. It visits everything reachable, but doesn't find the fewest steps.

In a sentence

  • “The puzzle game uses a depth-first search to try every path through the maze until it finds a way out.”

Level: Journeyman · More Data Structures terms at this level

Updated