Depth-First Search
A Graph Search algorithm:
- explore aggressively, backtrack only if needed
- uses FILO / recursion
Algorithm
DFS(graph $G$, start vertex $s$):
- mark $s$ as explored
- for every edge $(s, v)$
- if $v$ is unexplored
- DFS($G$, $v$)
running time $O(n + m)$
DFS applications
- Connected components like with Breadth-First Search
- Topological Ordering
- Strongly Connected Components