Graph Traversal on Grids

Why this module exists

Many interview problems are graphs in disguise. A 2D grid is just a graph where each cell is a node and edges connect adjacent cells (up, down, left, right). Once you see this, "grid problems" become "graph problems" — and you already know how to solve those.

This module teaches you to recognize graph structure in grids and apply BFS/DFS systematically.

1) Grids as Graphs

Consider a 4×5 grid:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

Each cell (row, col) is a node. Two nodes are connected if:

• They're adjacent (up, down, left, right)
• Both satisfy some condition (e.g., both are '1' for land)

This grid has 3 connected components (islands).

2) The Four Directions Pattern

Almost every grid problem uses this:

// Direction vectors: up, down, left, right
dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

for _, d := range dirs {
    nr, nc := row+d[0], col+d[1]
    if nr >= 0 && nr < rows && nc >= 0 && nc < cols {
        // (nr, nc) is a valid neighbor
    }
}

Some problems use 8 directions (include diagonals):

dirs := [][2]int{
    {-1, 0}, {1, 0}, {0, -1}, {0, 1},
    {-1, -1}, {-1, 1}, {1, -1}, {1, 1},
}

3) DFS on Grids

DFS explores as deep as possible before backtracking. For grids, it's often implemented recursively:

func dfs(grid [][]byte, row, col int, visited [][]bool) {
    // Bounds check
    if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) {
        return
    }
    // Already visited or not land
    if visited[row][col] || grid[row][col] == '0' {
        return
    }

    visited[row][col] = true

    // Explore all 4 directions
    dfs(grid, row-1, col, visited) // up
    dfs(grid, row+1, col, visited) // down
    dfs(grid, row, col-1, visited) // left
    dfs(grid, row, col+1, visited) // right
}

When to use DFS:

• Counting/marking connected components
• Flood fill (recoloring)
• Path existence (not shortest path)

4) BFS on Grids

BFS explores level by level. It guarantees shortest path in unweighted graphs.

func bfs(grid [][]byte, startRow, startCol int) {
    rows, cols := len(grid), len(grid[0])
    visited := make([][]bool, rows)
    for i := range visited {
        visited[i] = make([]bool, cols)
    }

    queue := [][2]int{{startRow, startCol}}
    visited[startRow][startCol] = true
    dirs := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

    for len(queue) > 0 {
        cell := queue[0]
        queue = queue[1:]
        row, col := cell[0], cell[1]

        for _, d := range dirs {
            nr, nc := row+d[0], col+d[1]
            if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
               !visited[nr][nc] && grid[nr][nc] == '1' {
                visited[nr][nc] = true  // Mark BEFORE enqueuing!
                queue = append(queue, [2]int{nr, nc})
            }
        }
    }
}

When to use BFS:

• Shortest path in unweighted graph
• Level-order traversal
• Finding nearest X

5) The Visited Set: Critical Detail

Mark when enqueuing, not when processing.

Wrong (causes duplicates):

queue = append(queue, neighbor)
// Later when processing:
if visited[neighbor] { continue }
visited[neighbor] = true

Right (prevents duplicates):

if !visited[neighbor] {
    visited[neighbor] = true  // Mark immediately
    queue = append(queue, neighbor)
}

If you mark too late, the same cell can be added to the queue multiple times from different neighbors.

6) Flood Fill Pattern

Flood fill changes all connected cells of one color to another:

func floodFill(image [][]int, sr, sc, newColor int) [][]int {
    oldColor := image[sr][sc]
    if oldColor == newColor {
        return image  // Critical: avoid infinite loop!
    }

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= len(image) || c < 0 || c >= len(image[0]) {
            return
        }
        if image[r][c] != oldColor {
            return
        }

        image[r][c] = newColor  // This acts as "visited"
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
    }

    dfs(sr, sc)
    return image
}

Key insight: Changing the color serves as the visited marker — no separate visited array needed.

Edge case: If oldColor == newColor, return immediately or you'll loop forever.

7) Counting Connected Components

To count islands (or any connected components):

func numIslands(grid [][]byte) int {
    if len(grid) == 0 {
        return 0
    }

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

    var dfs func(r, c int)
    dfs = func(r, c int) {
        if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == '0' {
            return
        }
        grid[r][c] = '0'  // Mark as visited by sinking the island
        dfs(r-1, c)
        dfs(r+1, c)
        dfs(r, c-1)
        dfs(r, c+1)
    }

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] == '1' {
                count++
                dfs(r, c)  // Sink entire island
            }
        }
    }

    return count
}

Pattern:

1. Scan the entire grid
2. When you find an unvisited land cell, increment count
3. DFS/BFS to mark the entire component as visited
4. Continue scanning

8) Common Mistakes

• Forgetting bounds checks: Always check 0 <= r < rows and 0 <= c < cols
• Not handling empty grid: Check len(grid) == 0 before accessing grid[0]
• Infinite loop in flood fill: When new color equals old color
• Marking visited too late: In BFS, mark before enqueuing
• Modifying input when you shouldn't: Sometimes you need a separate visited array

9) Complexity Analysis

For a grid with R rows and C columns:

The space for DFS can be O(R × C) if the grid is a long snake-like path.

Outcomes

After this module, you should be able to:

• Recognize when a grid problem is really a graph problem
• Implement DFS and BFS on 2D grids
• Use the four-directions pattern correctly
• Handle the visited set properly (mark early!)
• Count connected components
• Perform flood fill without infinite loops

Practice Set

1. Flood Fill (Easy) — Recolor a connected region
2. Number of Islands (Medium) — Count connected components

Start with Flood Fill to understand the basic DFS pattern on grids, then Number of Islands adds the component counting loop.