depth-first search
A graph search that follows one path as deep as it can go, then backs up to the last choice point and tries the next branch.
In more detail
Recursive DFS uses the call stack; iterative DFS uses an explicit stack. A visited set stops it looping forever on cycles, and it runs in O(V + E). It is the basis of cycle detection, topological ordering and backtracking.
Related terms
- breadth-first search — A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
- stack — A collection where the last item added is the first one removed, like a pile of plates.
- cycle detection — Finding whether a graph contains a cycle; in a directed graph, DFS with three colours finds one by spotting an edge back to a vertex still in progress.
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- set — Python's built-in unordered collection of unique items, implemented as a hash table that stores keys without values.
Taught in
- Stacks And Queues: Last In Or First In — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers