Pattern 20 of 27

Graph BFS and DFS

Explore connected cells or nodes with a visited mark, using DFS to cover whole components and BFS when you need the fewest steps.

Cost: O(V + E) time, O(V) space; O(rows × cols) on a grid
Problems: 6

When to reach for it

The input is a grid of cells or a list of edges.
The prompt asks to count regions, fill an area, or find a shortest path where every step costs the same.
Neighbours are defined by up, down, left, right, or by edges.

How it works

Every graph traversal needs three things: a way to list neighbours, a visited mark, and an order. DFS goes deep and suits counting or colouring connected components. BFS spreads outward one layer at a time, so the first time it reaches a cell is along a shortest path when all steps cost the same. Multi-source BFS starts with every source already in the queue, which is how Rotting Oranges measures elapsed minutes.

The template

Written for Number of Islands (write-up)

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"              # mark visited
        sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)

    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                sink(r, c)
    return islands

Open in the editor Trace it line by line

Six problems, in learning order

1.Number of IslandsLeetCode 200Sink each island with DFS and count how many times you start.Medium
2.Max Area of IslandLeetCode 695The same DFS, returning the size of each island.Not in the curated 370 yet.Medium
3.Flood FillLeetCode 733DFS from one cell, doing nothing if the new colour equals the old one.Easy
4.Rotting OrangesLeetCode 994Multi-source BFS from every rotten orange; the number of layers is the time.Medium
5.Shortest Path in Binary MatrixLeetCode 1091BFS in eight directions from the top-left corner.Not in the curated 370 yet.Medium
6.Number of Closed IslandsLeetCode 1254Sink islands touching the border first, then count what remains.Not in the curated 370 yet.Medium

What usually goes wrong

Marking a cell visited when it is popped instead of when it is pushed, which queues it many times.
Recursion depth on large grids; an explicit stack avoids it.
Forgetting diagonal moves when the prompt allows eight directions.

Graph BFS and DFS, answered

When should I use the graph bfs and dfs pattern?

The input is a grid of cells or a list of edges. The prompt asks to count regions, fill an area, or find a shortest path where every step costs the same. Neighbours are defined by up, down, left, right, or by edges.

What is the time complexity of graph bfs and dfs?

O(V + E) time, O(V) space; O(rows × cols) on a grid. Multi-source BFS starts with every source already in the queue, which is how Rotting Oranges measures elapsed minutes.

Which problem should I start with for graph bfs and dfs?

Start with Number of Islands (LeetCode 200, Medium). Sink each island with DFS and count how many times you start. The six problems on this page are in learning order.