Skip to content

Topic 13 of 20

Graphs (BFS, DFS, Grid)

Model problems as nodes and edges; traverse with DFS and BFS, on explicit graphs and on grids.

35 problems5 Easy25 Medium5 Hard

The concept

A graph is a set of nodes connected by edges, and a surprising number of problems become easy once you recognise one. A grid is a graph where each cell connects to its neighbours. A word ladder is a graph where words differing by one letter are connected. A lock is a graph whose nodes are its combinations. Most solutions start by building an adjacency list (or treating the grid as one implicitly) and then traversing it.

DFS goes deep before backtracking and is ideal for exploring connected components, flood fills and detecting cycles. BFS explores level by level with a queue, which makes it the right tool for shortest paths in unweighted graphs. Start BFS from many sources at once (multi-source BFS) and it computes distances to the nearest source in a single pass, as in Rotting Oranges or 01 Matrix.

Always track visited nodes, and think about how each node is represented (an index, a pair of coordinates, or an entire state string). Graph problems are a major part of Google and Amazon interviews, and this topic is the foundation for Advanced Graphs and much of dynamic programming.

Patterns you will learn

Problems, in order

  1. 1

    The simplest grid traversal; learn the neighbour loop here.

  2. 2

    Counting edges on a grid without a full traversal.

    Grid IterationReported at: MetaGoogleAmazon
  3. 3

    Build an adjacency list and run BFS/DFS on it.

    Connected ComponentsReported at: AmazonGoogle
  4. 4

    Reasoning with degrees instead of traversal.

    In/Out DegreeReported at: GoogleAmazonApple+1
  5. 5

    A quick drill on reading edge lists.

    Degree ReasoningReported at: Microsoft
  6. 6

    The most-asked graph problem; counting connected components on a grid.

    Grid DFS / Flood FillReported at: AmazonMicrosoftMeta+16
  7. 7

    DFS that returns component size.

    Grid DFS / Flood FillReported at: AmazonMetaMicrosoft+4
  8. 8

    Components from an adjacency matrix; also a Union-Find intro.

  9. 9

    Deep-copying a graph with an old → new map.

    DFS/BFS + Hash MapReported at: MetaAmazonGoogle+2
  10. 10

    Simple reachability over an implicit graph.

    DFS ReachabilityReported at: Amazon
  11. 11
  12. 12

    The canonical multi-source BFS; asked at Amazon constantly.

    Multi-source BFSReported at: AmazonMicrosoftVMware+1
  13. 13
    01 MatrixMedium

    Distances to the nearest zero with one BFS.

    Multi-source BFSReported at: GoogleAmazonMeta+1
  14. 14

    Multi-source BFS from all land cells.

  15. 15

    8-directional BFS for shortest paths.

    BFS Shortest Path (Unweighted)Reported at: MetaAmazonMicrosoft+3
  16. 16

    BFS with exit detection on the border.

  17. 17

    Search backwards from both oceans.

    Reverse Multi-source DFSReported at: GoogleAmazonUber+1
  18. 18

    Mark border-connected cells first, then flip the rest.

    Border DFSReported at: GoogleBloombergUber+1
  19. 19

    The same border trick, used for counting.

    Border DFSReported at: Google
  20. 20

    Excluding border-touching components.

  21. 21

    Component validation across two grids.

  22. 22
  23. 23

    Bipartiteness on an edge list.

  24. 24

    Cycle detection with white/grey/black DFS states.

  25. 25

    Tracking edge direction during traversal.

    DFS with Edge DirectionReported at: Amazon
  26. 26

    Longest weighted root-to-leaf path in a hierarchy.

    Tree DFS / BFSReported at: GoogleAmazon
  27. 27

    Answering ratio queries by path products.

    Weighted Graph DFSReported at: AmazonGoogleMeta+5
  28. 28

    BFS on a board with jumps (the Journey Map's namesake).

  29. 29

    BFS over lock states with dead ends.

  30. 30

    State-space BFS over a word bank.

  31. 31

    Shortest transformation with wildcard buckets; a Hard classic.

    Implicit Graph / State-space BFSReported at: AmazonMetaMicrosoft+4
  32. 32

    BFS where the state includes remaining eliminations.

  33. 33

    BFS on routes instead of stops.

  34. 34

    Label components, then test each flip.

  35. 35

    BFS over (node, visited-mask) states.