Command Palette

Search for a command to run...

Hectal

Module 22

Depth-First Search

Go deep, then back up: the DFS template, connected components, flood fill, working inward from the border, and enumerating paths.

Intermediate 4 lessons 8 problems ~45 min of lessons
Graph DFS and Flood Fill

Depth-first search follows one path as far as it can, then backs up to the last junction and tries the next branch. It's the natural fit for "explore everything connected to this" questions: counting islands, filling regions, checking whether all rooms can be reached, and listing every path.

DFS doesn't give shortest paths (that's BFS), but it's shorter to write, uses memory proportional to the depth, and its enter/leave timing is what cycle detection and topological sort are built on in the next two modules.

Best after: Graph Fundamentals, Recursion

Part 1

Learn the ideas

  1. 22.1The DFS TemplateMark the node, then recurse into every unvisited neighbour. Iteratively, the same thing with an explicit stack.12 min
  2. 22.2Components and Flood FillLoop over every node; each time you find an unvisited one, start a DFS that marks its whole component. The number of starts is the number of components.12 min
  3. 22.3Working Inward from the BorderWhen the question is "which cells can reach the edge?", reverse it: start DFS from the edge and mark everything reachable.10 min
  4. 22.4Enumerating Paths: DFS + BacktrackingTo list every path, keep the current path, add a node before recursing and remove it after. In a DAG no visited set is needed.10 min

Part 2

Solve the problems

In order of difficulty. Each one shows the pattern it teaches.

  1. 22.1Number of IslandsMediumGraph DFS and Flood Fill

    Counting connected components on a grid by sinking each island.

  2. 22.2Flood FillEasyGraph DFS and Flood Fill

    The paint-bucket tool: DFS over same-coloured neighbours.

  3. 22.3Max Area of IslandMediumGraph DFS and Flood Fill

    A DFS that returns a value: the size of the region it explored.

  4. 22.4Number of ProvincesMediumGraph DFS and Flood Fill

    Components when the graph is given as an adjacency matrix.

  5. 22.5Surrounded RegionsMediumGraph DFS and Flood Fill

    Mark the survivors from the border, then flip everything else.

  6. 22.6Pacific Atlantic Water FlowMediumGraph DFS and Flood Fill

    Two reverse searches from two borders, then intersect.

  7. 22.7All Paths From Source to TargetMediumGraph DFS and Flood Fill

    Path enumeration on a DAG with add / recurse / remove.

  8. 22.8Keys and RoomsMediumGraph DFS and Flood Fill

    Reachability from one node: is every node visited?