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