Many graph problems are presented as 2D grids where cells are nodes and adjacent cells are edges. DFS and BFS explore connected regions.
Use when: you need to find connected components, shortest paths, or flood-fill regions in a grid.
Count the number of islands in a grid. An island is a group of ‘1’s connected horizontally or vertically. We use DFS to “sink” each island as we find it.
DFS marks all connected land cells as visited by changing ‘1’ to ‘0’ (sinking the island).
Mark as visited.
Explore all 4 directions.
BFS version: find the shortest path in an unweighted grid. BFS guarantees the shortest path because it explores all cells at distance d before distance d+1.
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 {
return
}
if grid[r][c] != '1' {
return
}
grid[r][c] = '0'
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)
}
}
}
return count
}
func shortestPath(grid [][]int, sr, sc, er, ec int) int {
rows, cols := len(grid), len(grid[0])
if grid[sr][sc] == 1 || grid[er][ec] == 1 {
return -1
}
type point struct{ r, c int }
dirs := []point{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
queue := []point{{sr, sc}}
visited := make([][]bool, rows)
for i := range visited {
visited[i] = make([]bool, cols)
}
visited[sr][sc] = true
dist := 0
for len(queue) > 0 {
size := len(queue)
for i := 0; i < size; i++ {
p := queue[0]
queue = queue[1:]
if p.r == er && p.c == ec {
return dist
}
for _, d := range dirs {
nr, nc := p.r+d.r, p.c+d.c
if nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
!visited[nr][nc] && grid[nr][nc] == 0 {
visited[nr][nc] = true
queue = append(queue, point{nr, nc})
}
}
}
dist++
}
return -1
}
func main() {
grid := [][]byte{
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'},
}
fmt.Println("Islands:", numIslands(grid))
maze := [][]int{
{0, 0, 0, 0},
{1, 1, 0, 1},
{0, 0, 0, 0},
{0, 1, 1, 0},
}
fmt.Println("Shortest path:", shortestPath(maze, 0, 0, 3, 3))
}