Notes

Graphs — BFS/DFS

13 min read

must-know mid · part of Skills & Topics · Senior SWE Roadmap · related: Graphs — Shortest Path · Graphs — Union-Find & MST · Stacks & Queues · Backtracking · Hashing & Hash Maps

Why this matters / recognition signals

Almost every “is X reachable from Y,” “how many groups/regions,” “does this have a cycle,” or “process these in dependency order” problem is a graph traversal wearing a costume — a grid, a list of prerequisites, a list of accounts sharing an email. Recognizing the disguise is most of the work; once you see the graph, BFS and DFS are the two ways to walk it, and picking the right one is a small, mechanical decision.

Recognition signals:

  • “shortest path / fewest steps / minimum number of moves” in an unweighted graph or grid → BFS
  • “does a path exist,” “can you reach,” “explore all of a region/connected group” → either works, DFS is usually less code
  • “detect a cycle,” “can these tasks be ordered” (course prerequisites, build dependencies) → DFS with state tracking, or topological sort
  • “number of islands / provinces / connected components,” flood-fill style grid problems → BFS or DFS from every unvisited cell
  • “clone this graph,” “all paths between two nodes” → DFS with backtracking

This note covers graph representation (used by every graph note in this vault) plus BFS and DFS themselves. Graphs — Shortest Path builds on BFS for the weighted case (Dijkstra, Bellman-Ford). Graphs — Union-Find & MST covers an alternative, non-traversal way to answer connectivity questions.

Graph representation

A graph is just nodes (vertices) and connections (edges). There are two standard ways to store one, and the choice has real memory consequences.

Example graph (undirected, 6 nodes) used throughout this note:

flowchart LR
    N0((0)) --- N1((1))
    N0 --- N2((2))
    N1 --- N3((3))
    N2 --- N4((4))
    N3 --- N5((5))
    N4 --- N5

Adjacency list — for each node, store only its actual neighbors:

0: [1, 2]
1: [0, 3]
2: [0, 4]
3: [1, 5]
4: [2, 5]
5: [3, 4]

Adjacency matrix — an N x N grid where matrix[u][v] = 1 if an edge exists:

    0  1  2  3  4  5
0 [ 0, 1, 1, 0, 0, 0 ]
1 [ 1, 0, 0, 1, 0, 0 ]
2 [ 1, 0, 0, 0, 1, 0 ]
3 [ 0, 1, 0, 0, 0, 1 ]
4 [ 0, 0, 1, 0, 0, 1 ]
5 [ 0, 0, 0, 1, 1, 0 ]

Even at this tiny scale, 24 of the 36 cells are wasted zeros. That waste scales quadratically with node count while the list scales linearly with edge count — and for most real graphs (social graphs, road networks, dependency graphs), the number of edges is much closer to O(V) than to O(V²).

Concretely: a graph with 10,000 nodes and 20,000 edges (average degree 4 — sparse, like most real-world graphs). An adjacency list stores roughly O(V+E) ≈ 30,000 entries (10,000 list headers + 20,000 edge references; doubled to ~40,000 if the graph is undirected and each edge is stored in both directions’ lists). An adjacency matrix, regardless of how many edges actually exist, allocates 10,000² = 100,000,000 cells — over 3,000x more memory for the same graph, with the vast majority sitting at 0.

Adjacency listAdjacency matrix
SpaceO(V + E)O(V²)
Check if edge (u, v) existsO(degree(u))O(1)
Iterate all neighbors of uO(degree(u)) — no wasted workO(V) — scans every column, edge or not
Best forsparse graphs (E << V²) — most real graphsdense graphs (E ≈ V²), or when O(1) edge-existence checks matter more than memory

Default to adjacency lists unless the graph is known to be dense or you specifically need O(1) edge lookups. Grids (2D arrays) are a third, implicit representation — a cell’s neighbors are computed from index offsets (row±1, col±1) rather than stored anywhere, so no explicit adjacency structure is needed at all.

BFS — breadth-first search

BFS explores the graph in strict layers of increasing distance from the source: visit everything 1 edge away, then everything 2 edges away, and so on. It uses a queue (FIFO) — new neighbors go to the back of the line and get processed only after everything closer to the source is done. This layer-by-layer order is exactly why BFS is the tool for shortest path in an unweighted graph: the first time a node is reached, it’s necessarily via the fewest possible edges, because everything with fewer edges was already exhausted first.

flowchart TD
    subgraph L0["Level 0 — dist 0"]
        N0((0))
    end
    subgraph L1["Level 1 — dist 1"]
        N1((1))
        N2((2))
    end
    subgraph L2["Level 2 — dist 2"]
        N3((3))
        N4((4))
    end
    subgraph L3["Level 3 — dist 3"]
        N5((5))
    end
    N0 --> N1
    N0 --> N2
    N1 --> N3
    N2 --> N4
    N3 --> N5
    N4 -.->|"5 also reachable via 4 — same level either way"| N5

Trace: BFS from node 0 on the example graph (mark visited at enqueue time, not dequeue time — see pitfalls):

StepDequeueUnvisited neighbors foundNewly enqueuedQueue afterVisited set
1— (start)—0[0]{0}
201, 21, 2[1, 2]{0,1,2}
313 (0 already visited)3[2, 3]{0,1,2,3}
424 (0 already visited)4[3, 4]{0,1,2,3,4}
535 (1 already visited)5[4, 5]{0,1,2,3,4,5}
64none (2, 5 both visited)—[5]{0,1,2,3,4,5}
75none (3, 4 both visited)—[]{0,1,2,3,4,5}

Visit order: 0, 1, 2, 3, 4, 5 — nodes come out in exactly the level order shown in the diagram above.

DFS — depth-first search

DFS commits to one neighbor immediately and goes as deep as possible before backtracking, using a stack — either an explicit one, or the call stack via recursion. It doesn’t care about distance; it cares about exhausting one path fully before trying the next.

flowchart TD
    S0["dfs(0)"] --> S1["dfs(1) — first unvisited neighbor of 0"]
    S1 --> S3["dfs(3) — first unvisited neighbor of 1"]
    S3 --> S5["dfs(5) — first unvisited neighbor of 3"]
    S5 --> S4["dfs(4) — first unvisited neighbor of 5"]
    S4 --> S2["dfs(2) — first unvisited neighbor of 4"]
    S2 -.->|"0 and 4 both visited — return"| S4
    S4 -.->|"5 visited too — return"| S5
    S5 -.->|"3 visited too — return"| S3
    S3 -.->|"1 visited too — return"| S1
    S1 -.->|"2 already visited (via other branch) — return"| S0

Trace: DFS from node 0 (same graph, same adjacency-list neighbor order as above):

StepCallNeighbors of current nodeAction
1dfs(0)1, 2mark visited; 1 unvisited → recurse into 1
2dfs(1)0, 3mark visited; 0 already visited, skip; 3 unvisited → recurse
3dfs(3)1, 5mark visited; 1 already visited, skip; 5 unvisited → recurse
4dfs(5)3, 4mark visited; 3 already visited, skip; 4 unvisited → recurse
5dfs(4)2, 5mark visited; 2 unvisited → recurse; 5 already visited
6dfs(2)0, 4mark visited; both already visited → return
7(unwind back to 4, 5, 3, 1, 0 — every remaining neighbor already visited)done

Visit order: 0, 1, 3, 5, 4, 2 — a completely different order from BFS’s 0, 1, 2, 3, 4, 5, on the identical graph. That difference is the whole point: BFS fans out level by level, DFS plunges down one branch before considering any other.

BFS in practice — Number of Islands (grid BFS)

A grid where '1' is land and '0' is water; count the number of connected land regions (islands), where connectivity is 4-directional. The grid is the adjacency structure — neighbors are computed from (row±1, col) / (row, col±1) offsets instead of stored anywhere. Each unvisited land cell found by the outer scan starts a fresh BFS that flood-fills (and marks visited) its entire island, so it’s never counted twice — and the outer scan is what handles multiple disconnected islands, since a single BFS call only reaches one component.

Java

public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    boolean[][] visited = new boolean[rows][cols];
    int[][] directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
    int islands = 0;
 
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1' && !visited[r][c]) {
                islands++;
                Queue<int[]> queue = new LinkedList<>();
                queue.add(new int[] { r, c });
                visited[r][c] = true; // mark at enqueue time, not dequeue time
 
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    for (int[] d : directions) {
                        int nr = cell[0] + d[0], nc = cell[1] + d[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                                && grid[nr][nc] == '1' && !visited[nr][nc]) {
                            visited[nr][nc] = true;
                            queue.add(new int[] { nr, nc });
                        }
                    }
                }
            }
        }
    }
    return islands;
}

Python

from collections import deque
 
def num_islands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    islands = 0
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and not visited[r][c]:
                islands += 1
                queue = deque([(r, c)])
                visited[r][c] = True  # mark at enqueue time, not dequeue time
 
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in directions:
                        nr, nc = cr + dr, cc + dc
                        if (0 <= nr < rows and 0 <= nc < cols
                                and grid[nr][nc] == "1" and not visited[nr][nc]):
                            visited[nr][nc] = True
                            queue.append((nr, nc))
    return islands

DFS in practice — Course Schedule (cycle detection)

numCourses courses, and a list of prerequisite pairs [a, b] meaning “to take a you must first take b” — a directed edge a → b. Return whether it’s possible to finish all courses, which is exactly “does this directed graph have a cycle.” A 3-state marking is required, not a plain visited boolean: UNVISITED (never touched), IN_PROGRESS (currently on the active recursion path), DONE (fully explored, provably safe). A “back edge” to a node that’s IN_PROGRESS is a cycle; an edge to a DONE node is fine — it was already proven not to lead back to anything currently on the stack.

Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
    for (int[] p : prerequisites) {
        graph.get(p[0]).add(p[1]); // course p[0] depends on p[1]
    }
 
    int[] state = new int[numCourses]; // 0 = unvisited, 1 = in progress, 2 = done
    for (int course = 0; course < numCourses; course++) {
        if (state[course] == 0 && hasCycle(course, graph, state)) {
            return false;
        }
    }
    return true;
}
 
private boolean hasCycle(int course, List<List<Integer>> graph, int[] state) {
    state[course] = 1; // mark as "on the current recursion path"
    for (int next : graph.get(course)) {
        if (state[next] == 1) return true;                       // back edge -> cycle
        if (state[next] == 0 && hasCycle(next, graph, state)) return true;
    }
    state[course] = 2; // fully explored, safe forever
    return false;
}

Python

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    graph: list[list[int]] = [[] for _ in range(num_courses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)
 
    UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
    state = [UNVISITED] * num_courses
 
    def has_cycle(course: int) -> bool:
        state[course] = IN_PROGRESS
        for nxt in graph[course]:
            if state[nxt] == IN_PROGRESS:
                return True  # back edge -> cycle
            if state[nxt] == UNVISITED and has_cycle(nxt):
                return True
        state[course] = DONE
        return False
 
    return not any(state[c] == UNVISITED and has_cycle(c) for c in range(num_courses))

Complexity comparison

Traversal / structureTimeSpaceNotes
BFS, adjacency listO(V + E)O(V) (queue + visited set)guarantees shortest path in unweighted graphs
DFS, adjacency list (recursive)O(V + E)O(V) (recursion stack + visited set)path existence, cycle detection, topological sort
BFS/DFS, adjacency matrixO(V²)O(V)neighbor scan is O(V) per node instead of O(degree)
Number of Islands, grid R×CO(R·C)O(R·C) worst casegrid is the implicit adjacency structure

Common pitfalls

  • Marking visited at dequeue time instead of enqueue time (BFS): a node can be pushed onto the queue multiple times before it’s ever processed, wasting work and, in the worst case, blowing up the queue size. Mark visited the moment you enqueue.
  • Using DFS expecting a shortest path: DFS finds a path, not the shortest one — it commits to the first branch it finds and may reach a target node via a much longer route before ever trying the direct one. Only BFS’s level-by-level order guarantees shortest path in unweighted graphs.
  • Recursive DFS stack overflow: a deep or long chain-like graph (100k+ nodes in a line) can blow the call stack. Convert to an explicit iterative DFS with your own Deque/list acting as the stack — recursion is just simulating one.
  • Missing bounds checks in grid traversal: forgetting to check 0 <= nr < rows before indexing grid[nr][nc] throws or reads garbage. Always bounds-check before the value check, not after.
  • Two-state visited boolean for directed-graph cycle detection: a plain visited/unvisited flag can’t distinguish “currently on my recursion path” from “already fully explored and safe” — that’s exactly the false-positive/false-negative trap Course Schedule is designed to test. Use 3 states.
  • Forgetting disconnected components: one BFS/DFS call from a single start node only reaches its own component. Number of Islands’ outer double-loop over every cell — starting a fresh traversal from every still-unvisited cell — is the general pattern for “count/process every component,” not a grid-specific trick.

Practice problems

  • Number of Islands (grid BFS/DFS, multi-component flood fill)
  • Course Schedule / Course Schedule II (cycle detection, topological sort)
  • Clone Graph (BFS or DFS with a visited-node map to handle cycles in the input graph itself)
  • Word Ladder (BFS shortest transformation sequence — implicit graph, words are nodes)
  • Rotting Oranges (multi-source BFS — seed the queue with every rotten cell up front)
  • Pacific Atlantic Water Flow (DFS/BFS run inward from both border sets, then intersect)
  • Number of Connected Components in an Undirected Graph (BFS/DFS, or union-find — see Graphs — Union-Find & MST)

Interview angles

  • “Why does BFS guarantee shortest path in an unweighted graph but DFS doesn’t?” — BFS explores in strict layers of increasing edge-distance, so the first time any node is dequeued it’s necessarily via the fewest possible edges; DFS commits to one path immediately and may reach a node via a longer route long before trying the short one.
  • “When would you pick DFS over BFS even though both are O(V+E)?” — when you need full paths rather than shortest distance (backtracking, path existence, cycle detection, topological sort); DFS’s implicit call-stack is a more natural fit, and on graphs that are wide but shallow, BFS’s frontier (queue) can hold far more nodes at once than DFS’s stack ever does.
  • “How do you detect a cycle in a directed graph vs. an undirected graph?” — directed: 3-state DFS (unvisited/in-progress/done), a back edge to an in-progress node is a cycle; undirected: 2-state suffices, but you must track the parent so the edge back to your immediate parent isn’t mistaken for a cycle.
  • “Your recursive DFS stack-overflows on a large input — what now?” — convert to an explicit, iterative stack-based DFS; the recursion was only ever simulating a stack, so replace it with a real one you push/pop by hand.
  • “There are multiple disconnected components — does one BFS/DFS call find everything?” — no; loop over every node and start a fresh traversal only from still-unvisited ones. This is exactly the number-of-islands / number-of-connected-components pattern.
  • “For a grid problem, do you need to build an adjacency list?” — no; each cell’s up-to-4 (or 8) neighbors are computed on the fly from index offsets, so the grid’s own indices act as the graph — building an explicit adjacency list would be wasted memory and setup work.

My Notes

Graph View

Backlinks