Graphs, BFS and DFS patterns

A graph is a set of nodes (vertices) connected by edges. Edges can be directed (one way) or undirected, and may carry weights (costs). Graphs model maps, social networks, web links, task dependencies and grids.

Representing a graph

Adjacency list: for each node, a list of its neighbours. Uses O(V + E) space. The usual choice.
Adjacency matrix: a V by V table. Fast edge lookup, O(V²) space, good for small or dense graphs.
Edge list: a list of pairs. Simple input format.

// edges: [[0,1],[0,2],[1,3]]  (undirected)
function buildGraph(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { graph[a].push(b); graph[b].push(a); }
  return graph;
}

Many problems give a grid instead. Each cell is a node, and its neighbours are up, down, left and right (check the bounds).

Depth-first search (DFS)

Go as deep as possible along one path, then backtrack. Use recursion or an explicit stack. Keep a visited set so you do not loop forever on cycles.

function dfs(graph, start) {
  const visited = new Set();
  function go(node) {
    visited.add(node);
    for (const next of graph[node]) if (!visited.has(next)) go(next);
  }
  go(start);
  return visited;
}
// Time O(V + E), space O(V)

Good for: finding connected components, detecting cycles, topological sort, exploring all paths and flood fill.

Breadth-first search (BFS)

Explore level by level using a queue. In an unweighted graph, BFS finds the shortest path (fewest edges) from the start.

function shortestPath(graph, start, target) {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  for (let i = 0; i < queue.length; i++) {      // index pointer avoids slow shift()
    const node = queue[i];
    if (node === target) return dist.get(node);
    for (const next of graph[node]) {
      if (!dist.has(next)) { dist.set(next, dist.get(node) + 1); queue.push(next); }
    }
  }
  return -1;
}
// Time O(V + E), space O(V)

Mark nodes visited when you enqueue them, not when you dequeue them, to avoid adding the same node many times.

Pattern 1: grid and flood fill (Number of Islands)

Count groups of connected 1s in a grid.

function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let count = 0;
  function sink(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] !== "1") return;
    grid[r][c] = "0";                          // mark visited
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
  }
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === "1") { count++; sink(r, c); }
  return count;
}
// Time O(rows * cols)

Note: this modifies the input. Mention it, or use a separate visited set. Very deep recursion on a huge grid can overflow the stack, so BFS or an explicit stack may be safer.

Multi-source BFS: start the queue with many cells at once (for example Rotting Oranges, 01 Matrix).

Pattern 2: cycle detection

Undirected graph: during DFS, reaching a visited node that is not the parent means a cycle.
Directed graph: use three states (unvisited, in the current path, done). Reaching a node that is in the current path means a cycle.

Pattern 3: topological sort (dependencies)

For a directed acyclic graph (DAG), produce an order where every edge goes from earlier to later. Used for course schedules and build order.

Kahn's algorithm (BFS):

Count each node's in-degree (incoming edges).
Queue all nodes with in-degree 0.
Pop a node, add it to the order, and decrease the in-degree of its neighbours, queueing any that reach 0.
If the order has fewer nodes than the graph, there is a cycle.

function canFinish(n, prerequisites) {
  const graph = Array.from({ length: n }, () => []), indeg = new Array(n).fill(0);
  for (const [course, pre] of prerequisites) { graph[pre].push(course); indeg[course]++; }
  const queue = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) queue.push(i);
  let done = 0;
  for (let i = 0; i < queue.length; i++) {
    done++;
    for (const next of graph[queue[i]]) if (--indeg[next] === 0) queue.push(next);
  }
  return done === n;
}

Pattern 4: connected components and Union-Find

To track which nodes are connected as edges arrive, Union-Find (disjoint set) supports find and union in almost O(1) with path compression. Use it for "number of connected components", "redundant connection" and Kruskal's minimum spanning tree.

Beyond unweighted graphs

Dijkstra's algorithm: shortest paths with non-negative weights, using a priority queue, O((V + E) log V).
Bellman-Ford: handles negative weights.
0-1 BFS and A* are useful variants.

Choosing DFS or BFS

Goal	Prefer
Shortest path in an unweighted graph	BFS
Count components, flood fill	Either
Cycle detection, topological order, all paths	DFS (or Kahn's BFS)
Very deep graph (stack overflow risk)	BFS or iterative DFS

Common mistakes

Forgetting the visited set, causing infinite loops.
Marking visited too late in BFS.
Not handling disconnected graphs (loop over every node as a start).
Wrong grid bounds, or revisiting cells.
Confusing directed and undirected edges when building the graph.

Practice problems

Number of Islands, Clone Graph, Rotting Oranges, Course Schedule, Course Schedule II, Pacific Atlantic Water Flow, Word Ladder, Number of Connected Components, Network Delay Time.

Takeaway: build an adjacency list, use BFS for shortest paths and level order, DFS for components and cycles, Kahn's algorithm for dependencies, and always track visited nodes.

Interview prep and DSA series, Part 2 (data structures and behaviour): 3 of 5. Previous: Binary trees and BSTs: traversals and interview patterns.

Graphs, BFS and DFS: how to solve graph interview problems