DFS explores as deep as possible before backtracking. Implementation: recursion (using the implicit call stack) or an explicit stack. Either way, you also need a "visited" set.
Recursive template
``` function dfs(u): mark u visited for each neighbor v of u: if v not visited: dfs(v) ```
That's it. The shape of the algorithm changes only in what you do at the "enter" and "leave" points of each node.
Complexity
, same as BFS. Space is for the visited set plus for the recursion stack, where is the depth.
What DFS is good for
- Cycle detection in directed graphs: track the recursion stack; if you encounter a vertex that's on the current stack, you've found a back edge — a cycle exists.
- Connected components: repeated DFS from each unvisited vertex.
- Topological sort: see the next lesson.
- Bridges and articulation points: Tarjan's algorithms, both built on DFS.
- Strongly connected components: Kosaraju's or Tarjan's, both DFS-based.
Iterative DFS
Replace recursion with an explicit stack of vertices to process. The order isn't strictly the same as recursive DFS (post-order is awkward iteratively), but reachability and cycle detection still work. Switch to iterative when depth could overflow the call stack.
DFS vs BFS
Both visit all reachable vertices in . Use BFS for shortest paths in unweighted graphs. Use DFS for everything else where order matters — topological sort, cycle detection, tree-like properties. Both are templates; the interesting algorithm lives in what you record at each visit.