Gitter als Graphen
Inseln zählen, Flood Fill, kürzester Weg im Labyrinth - 2D-Gitter sind Graphen, in denen jede Zelle mit ihren Nachbarn verbunden ist, und BFS/DFS lösen sie direkt.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
A huge fraction of "graph" interview problems don't hand you a graph at all - they hand you a 2D grid. Islands in a map, flood fill in a paint program, the shortest path through a maze, rotting oranges spreading to neighbors: all of these are graphs in disguise, where each cell is a node connected to its neighbors. Recognizing this unlocks them instantly.
A grid is a graph
In a grid problem, each cell is a node, and each cell is connected to its orthogonal neighbors (up, down, left, right - sometimes diagonals too). You don't build an explicit adjacency list; the neighbors are computed from the coordinates:
// the four neighbors of cell (r, c)
int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) { // stay in bounds
// (nr, nc) is a neighbor
}
}Once you see the grid as a graph, BFS and DFS apply directly - the only additions are bounds checking and marking visited cells (often by mutating the grid itself).
Counting islands with DFS
The classic "number of islands" problem: given a grid of land (1) and water (0), count the connected land masses. Each island is a connected component - a group of cells reachable from each other. DFS from each unvisited land cell floods the whole island, so the number of DFS launches is the number of islands:
// number of islands — O(rows * cols)
int numIslands(char[][] grid) {
int count = 0;
for (int r = 0; r < grid.length; r++)
for (int c = 0; c < grid[0].length; c++)
if (grid[r][c] == '1') {
count++;
sink(grid, r, c); // flood this island so it's not counted again
}
return count;
}
void sink(char[][] grid, int r, int c) {
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != '1') return;
grid[r][c] = '0'; // mark visited by sinking the land
sink(grid, r + 1, c); sink(grid, r - 1, c);
sink(grid, r, c + 1); sink(grid, r, c - 1);
}Each cell is visited once, so it's O(rows × cols). Mutating the grid to '0' is a neat way to mark visited without a separate set (mention to your interviewer that you're modifying the input).
Multi-source BFS for 'spreading' problems
Some grid problems spread from many starting points at once - 'rotting oranges' infecting neighbors each minute, or the nearest distance to any of several sources. The trick is multi-source BFS: seed the queue with all sources at distance 0, then BFS outward. The level count gives the time for everything to be reached, in one pass.
Picture a tiled floor where you spill paint on one tile. The paint spreads to each touching tile of the same color, then to their neighbors, filling one connected region but stopping at grout lines of a different color (walls or water). That's flood fill - a DFS or BFS from the spill point across connected same-type cells. Counting islands is spilling a bucket on each unpainted land tile you find and seeing how many separate spills it takes to cover all the land: one spill per island.
In a grid, cells are empty (0), a fresh orange (1), or a rotten orange (2). Every minute, a rotten orange rots any fresh orange orthogonally adjacent to it. Return the minutes until no fresh orange remains (or -1 if impossible). Explain which traversal fits and how you track the minutes.
How do you treat a 2D grid as a graph for BFS/DFS?
Key takeaways
- Many 'graph' problems are 2D grids: each cell is a node connected to its orthogonal neighbors.
- Compute neighbors from coordinates with bounds checks; no explicit adjacency structure needed.
- Counting connected components (islands) = launching DFS/BFS from each unvisited cell; flood the component so it's counted once.
- Mutating the grid to mark visited avoids a separate visited set (note you're modifying the input).
- Multi-source BFS (seed all sources at level 0) solves 'spreading' problems like rotting oranges and nearest-source distance.