BFS and DFS on graphs

There are two ways to traverse a graph, and both share the same skeleton: take the next node → process it if unseen → push its neighbours. The only difference is which collection you take from.

BFS (breadth-first search) uses a queue (FIFO) and walks the graph layer by layer: first everything one step from the start, then everything two steps away. That is exactly why BFS finds the shortest path in an unweighted graph: the moment you first reach a node, you reached it in the minimum number of steps.

DFS (depth-first search) uses a stack (LIFO) or recursion and goes all the way down one direction, then backtracks and tries another branch. DFS does not find shortest paths, but it is indispensable for questions about the structure of the graph.

Both are O(V + E): each vertex is processed once and each edge examined once (twice in an undirected graph). Memory is O(V).

A visited set is mandatory. This is the most commonly skipped detail in graph traversal, and it shows up immediately in an interview.

A tree needs no visited set because a tree has no cycles — there is exactly one path to each node. In a graph two nodes can point at each other, and without visited you fall into the infinite loop A → B → A → B ....

Two subtle points:

• Mark a node visited when you push it onto the queue, not when you pop it. Otherwise the same node lands in the queue several times, and on large graphs that blows up memory
• Recursive DFS can go V deep. On a chain-shaped graph of 10⁵ nodes that means a stack overflow — write DFS iteratively with an explicit stack in such cases

The three classic uses of DFS:

• Connectivity / connected components — how many separate "islands" exist; you start a fresh DFS from every unvisited node
• Cycle detection — in a directed graph, hitting a node that is currently on the recursion stack means a cycle (that is a set SEPARATE from visited); in an undirected graph you exclude the parent you came from
• Topological sort — DFS on a DAG collects nodes as it finishes them, and you reverse the list at the end; the result is an order that violates no dependency (build order, migration order)

Grid problems are disguised graph problems, and they are the graph tasks asked most often in interviews: number of islands, flood fill, rotting oranges, shortest path in a maze, largest lake area.

The conversion rule is simple: each cell is a vertex, adjacent cells are edges. You don't build a Graph class — you compute neighbours from offsets:

• 4 directions: [[0,1],[1,0],[0,-1],[-1,0]]
• 8 directions (with diagonals): additionally [[1,1],[1,-1],[-1,1],[-1,-1]]

Two rules: check bounds on every step (0 <= r < rows && 0 <= c < cols), and either keep visited as a separate matrix or (if allowed) mutate the cell in place.

Which to pick? If the question is "how many islands / how large is this area" → DFS (or BFS, it doesn't matter). If it is "the minimum number of steps / how many minutes until it spreads" → BFS, always. That last case often needs multi-source BFS: you seed the queue with every starting point at once and the same layering works.