Depth-First Search
Dives as deep as possible before backtracking, using a stack (or recursion). The skeleton under cycle detection, topological sort, maze generation, and connected components.
- Category
- Graphs
- Time complexity
- O(V + E)
- Space complexity
- O(V)
Pseudocode
stack ← [start] visit top, push new neighbours backtrack when stuck order = deep-first
Reference implementation
def dfs(n):
seen.add(n)
for m in adj[n]:
if m not in seen:
dfs(m) # backtracks