BFS / DFS

DFS (Depth-First Search)

Start at a node, go as deep as possible along one path, then backtrack and try other paths. Uses recursion or an explicit stack. Great for connectivity, cycle detection, and exploring all possible paths.

O(V + E)

O(V)

How It Works

Depth-first search dives along one path as far as possible before backtracking. Implemented with recursion or an explicit stack, it marks each node visited on arrival, then recursively explores each unvisited neighbor. When a node has no unexplored neighbors left, the call returns and control backtracks to try the next branch. This ordering naturally uncovers structure: back edges reveal cycles, finish times drive topological sort, and full exhaustion of a component tells you its size.

Like BFS, the total work is O(V + E) since every vertex and edge is touched a constant number of times — a huge improvement over enumerating paths, whose count can be exponential. The recursion stack can grow to O(V) in the worst case (a long chain), so deep graphs sometimes require an iterative stack to avoid overflow.

Step-by-Step Visualization

DFS from node 0. Go deep before going wide

Stack[0]

Visited{0}

1/4

Code

Java

static void dfs(List<List<Integer>> graph, int start, Set<Integer> visited) {
  visited.add(start);
  for (int neighbor : graph.get(start)) {
    if (!visited.contains(neighbor)) dfs(graph, neighbor, visited);
  }
}

Tips & Gotchas

1Use a stack (or recursion). Go as deep as possible first

2Mark nodes as visited to avoid cycles

3DFS is good for: topological sort, cycle detection, connected components

Practice Problems

1Number of Islands
2Clone Graph
3Pacific Atlantic Water Flow
4Max Area of Island
5Flood Fill

About the BFS / DFS Pattern

The two fundamental ways to explore a graph. DFS goes as deep as possible before backtracking (uses a stack or recursion). BFS explores all neighbors first before going deeper (uses a queue). Both visit every node exactly once.

Key insight

Start with: is it directed or undirected? Weighted or unweighted? Then pick the right tool: BFS for shortest unweighted path, Dijkstra for weighted, topological sort for DAG ordering, union-find for components.

Common Graphs Interview Problems

Number of Islands
Clone Graph
Course Schedule
Pacific Atlantic Water Flow
Network Delay Time
Minimum Spanning Tree
Word Ladder

Frequently Asked Questions

Is recursive DFS ever a problem in interviews?

Yes — on grids or graphs with hundreds of thousands of nodes, recursion depth can exceed the language's stack limit, especially in Python. Mention the risk and be ready to convert to an iterative version with an explicit stack; the logic is identical.

How does DFS detect a cycle in an undirected graph?

While exploring, if you reach a visited node that is not the immediate parent of the current node, you have found a cycle. The parent exception matters because the edge you just came through would otherwise be a false positive.