Lesson 20.3 · Graph Fundamentals

Grids Are Graphs

In a 2D grid each cell is a node and its up/down/left/right cells are its neighbours. A direction array and a bounds check replace the adjacency list.

10 min

Think of it like this

A chessboard where a king may only step to the four squares sharing a side: the board itself is the graph, so you never need to write the connections down.

1.Neighbours on the fly

Use int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}} and, for cell (r, c), try (r + dr, c + dc), skipping anything outside 0 ≤ r < rows, 0 ≤ c < cols. Add the four diagonals for 8-directional movement.

When a single number per cell is handy (for visited sets or union-find), use id = r × cols + c and recover r = id / cols, c = id % cols.

Main.java

public class Main {
    public static void main(String[] args) {
        int rows = 3, cols = 4;
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int r = 0, c = 1;
        StringBuilder sb = new StringBuilder();
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;   // off the board
            sb.append("(").append(nr).append(",").append(nc).append(") ");
        }
        System.out.println(sb.toString().trim());
        System.out.println("id of (2,3) = " + (2 * cols + 3));
    }
}

Output

(1,1) (0,2) (0,0)
id of (2,3) = 11

Remember

Cells are nodes; shared sides are edges.
Direction arrays + bounds checks.
Flatten with r × cols + c.

Common mistakes

Checking bounds after indexing the array (ArrayIndexOutOfBoundsException).
Mixing up rows and columns in the flat id.

Command Palette

Grids Are Graphs

1.Neighbours on the fly