Graphs & BFS/DFS

How to recognize it

Graph problems describe connections between entities: friendships, flights between cities, prerequisites between courses, or adjacency in a grid (every cell connects to its up/down/left/right neighbors — grid problems are graph problems wearing a 2D array). The question usually asks about reachability ("can you get from A to B"), grouping ("how many separate islands"), or shortest path ("minimum number of hops").

How the pattern works

A representative BFS problem: find the shortest path length between two nodes in an unweighted graph. Process nodes level by level with a queue; the first time you reach the target, the number of levels traversed is guaranteed to be the shortest path, because BFS never explores a longer path before a shorter one exists.

from collections import deque

def shortest_path(graph, start, target):
    if start == target:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == target:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

function shortestPath(graph, start, target) {
  if (start === target) return 0;
  const visited = new Set([start]);
  const queue = [[start, 0]];
  let head = 0;
  while (head < queue.length) {
    const [node, dist] = queue[head++];
    for (const neighbor of graph[node]) {
      if (neighbor === target) return dist + 1;
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1;
}

Say why BFS and not DFS: "since edges are unweighted, the first time BFS reaches the target is guaranteed to be via the fewest hops — DFS could reach it via a much longer path first." That justification is the actual algorithmic insight; a correct DFS solution to a shortest-path question, without that insight, would need extra bookkeeping to even be correct.

Common mistakes

• Marking a node visited when it is dequeued/popped instead of when it is enqueued/pushed — this lets the same node get added to the queue multiple times before it is ever marked, wasting work and sometimes causing wrong answers
• Using DFS for a shortest-path question without realizing DFS provides no shortest-path guarantee at all
• Forgetting that a grid needs boundary checks (row/column within range) in addition to the visited check before recursing or enqueueing a neighbor
• Not clarifying whether the graph is directed or undirected before choosing how to build the adjacency structure — this changes whether an edge needs to be added in both directions

Complexity

Both BFS and DFS are O(V + E) time — every vertex and every edge is visited a constant number of times — and O(V) space for the visited set plus the queue or recursion stack. State it as V + E explicitly rather than just "O(n)": on a dense graph, E can be much larger than V, and naming both terms shows you understand where the cost actually comes from. See Time & Space Complexity.