A Graph Search algorithm:

- explore aggressively, backtrack only if needed
- uses FILO / recursion

DFS(graph $G$, start vertex $s$):

- mark $s$ as explored
- for every edge $(s, v)$
- if $v$ is unexplored
- DFS($G$, $v$)

running time [math]O(n + m)[/math]

- Connected components like with Breadth-First Search
- Topological Ordering
- Strongly Connected Components