Graphs: BFS & DFS

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A graph = vertices + edges. Store it as an adjacency list List<List<Integer>>: O(V + E) memory. Grids and puzzles are graphs too.

   #1
2. ↯use it when

   Fewest steps with equal-cost moves → BFS. Count or mark everything connected → DFS or BFS. Many sources spreading at once → multi-source BFS.

   #2
3. { }template

   BFS: offer(s); seen[s] = true; while the queue isn't empty: u = poll(); for each neighbour v not seen → mark it, offer(v).

   #3
4. O( )cost

   BFS and DFS: O(V + E) time, O(V) extra space. A grid is O(rows × cols). Bipartite and cycle checks cost the same.

   #4
5. !trap

   Mark visited when you enqueue, not when you poll — or the same vertex is queued many times.

   #5
6. !trap

   Recursive DFS on a big grid can go rows × cols deep → StackOverflowError. Use BFS or an ArrayDeque stack.

   #6
7. !trap

   Check bounds before grid[nr][nc], and loop over every vertex as a start, or disconnected parts are silently skipped.

   #7
8. !trap

   Directed cycle check needs 3 colours: only an edge into a gray (on-path) vertex is a cycle. A diamond is not.

   #8
9. ✦pro tip

   Seed the queue with every source (rotten oranges, gates, zeros): one BFS instead of one per source.

   #9
10. ✦pro tip

    "Fewest moves" puzzles (words, genes, dice boards, knights) are BFS on an implicit graph: states = vertices, moves = edges.

    #10

Shaky on a card? Open the chapter or flip its recall cards.