Implicit Graphs

Grid-based Graphs

In many competitive programming and robotics problems, graphs are not explicitly stored. Instead, a 2D Grid serves as an implicit graph where each cell (r, c) is a vertex, and edges connect adjacent cells.

VerticesRows × Cols

Max Degree4 or 8

Implicit Adjacency

We don't need an adjacency list. We can calculate neighbors on-the-fly using direction arrays like dx = [0,0,1,-1].

Boundary Checks

Crucial for grid traversal: always ensure 0 ≤ r < R and 0 ≤ c < C before accessing grid[r][c].

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

4,0

4,1

4,2

4,3

4,4

Loading Lab...

Implicit Graphs

Grid-based Graphs

VerticesRows × Cols

Max Degree4 or 8

Implicit Adjacency

We don't need an adjacency list. We can calculate neighbors on-the-fly using direction arrays like dx = [0,0,1,-1].

Boundary Checks

Crucial for grid traversal: always ensure 0 ≤ r < R and 0 ≤ c < C before accessing grid[r][c].

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

4,0

4,1

4,2

4,3

4,4

Grid Based Graphs

Grid Based Graphs

Grid-based Graphs

Implicit Adjacency

Boundary Checks

Grid-based Graphs

Implicit Adjacency

Boundary Checks