DFS (Depth-First Search)
Depth-first search (DFS) goes all the way down one branch before backing up to the next, usually implemented with recursion or an explicit stack.
DFS suits problems that need to explore a structure completely: counting connected components, detecting cycles, topological sorting. Memory is proportional only to the depth, but you must mark nodes as "visited" so you don't walk in circles forever.
Like walking a maze — go deep down one corridor until you hit a wall, then back up.
- Compared with BFS: BFS spreads a message to everyone ring by ring, while DFS goes down one corridor to the very end before turning back.
- It fits when you need to go through every branch: listing paths, checking for cycles, finding connected components.
How to spot it
When you see these cues in the problem, reach for DFS (Depth-First Search)
| Keyword in the problem | Why it points to this topic |
|---|---|
| enumerate all paths | DFS exhausts one branch before backtracking |
| detect cycles | DFS plus visited and recursion-stack tracking |
| connected components | Count components via DFS sweeps |
| topological sort | DFS post-order on a DAG |
When to use
3 typical situations where this topic applies
You need to traverse a whole graph / tree: list every vertex and every edge
The problem is naturally recursive: divide and conquer, backtracking, topological sort
Cycle detection, finding connected components, "flood fill" problems
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
You need the shortest path in an unweighted graph: BFS guarantees the shortest path, DFS does not
The graph is very deep (depth > 10^4): recursion causes a stack overflow → use iterative DFS with an explicit stack
You need to process level by level (level-order): BFS matches the problem better
Illustration
Press Play to see each step.
- Current
- In stack
- Visited
// DFS with an explicit stack — go deep down one branch firstfunction dfs(start) { const stack = [start] const visited = new Set() while (stack.length > 0) { const node = stack.pop() if (visited.has(node)) continue visited.add(node) // reverse to visit neighbors in adjacency order for (const nb of [...adj[node]].reverse()) { if (!visited.has(nb)) stack.push(nb) } }}Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function dfs(node: Node, graph: Graph, visited = new Set<Node>()): R {
if (visited.has(node)) return
visited.add(node)
// Pre-order: handle the node before recursing
visit(node)
for (const next of graph.neighbors(node)) {
dfs(next, graph, visited)
}
// Post-order: optional handling on the way back up
// postVisit(node)
}Recap
A quick summary — reread it before your interview
Key points
DFS uses a stack (recursion uses the call stack, the iterative version uses an explicit stack)
Mark visited before recursing into a child → avoids revisiting
DFS does not guarantee the shortest path — use BFS for unweighted graphs and Dijkstra for weighted ones
Pre-order, in-order, and post-order on a binary tree are all variants of DFS
Common mistakes
Forgetting to mark visited → infinite loop on a graph with cycles
Confusing DFS with BFS when you need the shortest path (DFS does not guarantee the shortest)
Stack overflow from deep recursion on a large graph — consider iterative DFS
Complexity
Time O(V + E), Space O(V) cho stack — V là số đỉnh, E là số cạnhPractice problems for this topic
Grouped by difficulty — work through them in order to build confidence