Grids and graphs cost terms

Why this matters

Many programs work on a map. A game moves a character across a board. A maze solver looks for a path from the entrance to the exit. A route planner looks at roads between towns. All of these store the same kind of thing: a set of places, and a set of links between them. The cost of the program depends on how many places and how many links it has to visit.

Before you can say how fast a walk over a map is, you need names for the sizes. This lesson gives you four of them. Rows and columns describe a grid. Vertices and edges describe a graph. Once you use these four names in your cost formulas, you can compare two programs fairly, even when the maps have different shapes.

The lesson on counting steps and Big-O shows how to turn a count into a growth rate. The lesson on hash table costs explains why a lookup in a hash table is fast on average. Here the job is smaller: choose the right variables, count the work in them, and see how the way you store the map changes the count.

Grids: a table of cells

A grid is a table with a fixed number of rows and columns. Each box in the table is called a cell. A chess board is a grid of 8 rows and 8 columns. A spreadsheet is a grid with many more rows and columns.

Use these two letters for a grid:

• R is the number of rows.
• C is the number of columns.

The number of cells is R times C. A grid with 3 rows and 4 columns has 3 × 4 = 12 cells. The grid is written as 3 x 4 in many texts, and "3 x 4" means 3 rows and 4 columns.

A walk over a grid visits cells one at a time. The most common walk is a breadth-first search, which visits every cell that can be reached from a starting cell. We will use it as the example. A breadth-first search keeps a queue of cells to visit. It takes one cell off the front of the queue, looks at its neighbours, and adds any new neighbour to the back of the queue. A neighbour is a cell directly above, below, left or right of it.

Here is a breadth-first search over a grid. It counts two things: how many cells it takes off the queue, and how many neighbour positions it checks.

grid size, rows x cols, cells, cell visits, neighbour checks
3 x 4, 12, 12, 48
10 x 10, 100, 100, 400
100 x 100, 10000, 10000, 40000
200 x 300, 60000, 60000, 240000
 
grid with a wall column (3 x 5, middle column blocked)
(6, 24)

Read the table with the four variables in mind. The cell visits column equals the number of cells, R times C, when every cell can be reached. The neighbour checks column is always 4 times the cell visits, because the code checks four directions for each cell it takes off the queue. The neighbour checks grow with R times C, not with R plus C.

What the cost is, in plain words

The cost of a full grid walk is about R times C. This is the number of cells, and each cell does a fixed amount of work: four neighbour checks and a few steps to update the queue. We write the cost as O(R × C). The Big-O notation is explained in the lesson on counting steps and Big-O. Here it only means "grows like this product".

The wall example shows a point that beginners miss. The grid is still 3 rows and 5 columns, so R times C is 15. But the walls block the middle column, so the search reaches only the 6 cells on the left side. The cost went down to 6 cell visits and 24 neighbour checks, because the cost depends on how many cells are reached, not only on the size of the table. In the worst case, when nothing is blocked, the cost is the full R times C.

Why not rows plus columns

A common mistake is to think that a walk along one row or one column costs R or C, so a walk across the grid costs R plus C. That is true for a single straight line of cells, but a search does not walk one line. It looks at every cell, because it must check whether a cell is the target or a dead end. So the total is the number of cells, not the sum of the two sides.

The same mistake shows up with a wall of cells. If a grid is 100 by 100, a walk along one row is 100 cells. A walk over the whole grid is 10,000 cells. The number 10,000 is R times C, and writing it as 200 would undercount the work by a factor of 50.

Graphs: dots and lines

A graph is a set of points joined by lines. The points are called vertices, and the lines are called edges. A vertex is one place. An edge says that two places are linked. A grid is a special kind of graph where each cell is a vertex and each pair of neighbouring cells has an edge between them. A road map is a graph. A friendship list is a graph. A graph does not need a regular shape, so it can describe almost any set of links.

Use these two letters for a graph:

• V is the number of vertices.
• E is the number of edges.

For the small graph below there are 5 vertices and 4 edges. The vertices are numbered 0 to 4. The edges join 0 to 1, 0 to 2, 1 to 2 and 2 to 3. The vertex 4 has no edges at all. A vertex with no edges still counts in V.

A graph can have edges that point one way, such as "follows" on a social site, or edges that go both ways, such as "is next to" on a road. In this lesson every edge goes both ways, so each edge is stored twice. When you count E, count each linked pair once.

Two ways to store a graph

The cost of a walk depends on how the graph is stored. The lesson will use two common forms: an adjacency list and an adjacency matrix.

An adjacency list keeps one list for each vertex. The list for a vertex holds the vertices it is linked to. An adjacency matrix keeps a table of V rows and V columns. The cell in row i and column j is 1 if there is an edge from i to j, and 0 if there is not.

This code builds both forms for the same small graph and prints them. It also counts the work needed to read the neighbours of one vertex in each form.

adjacency list:
0 [1, 2]
1 [0, 2]
2 [0, 1, 3]
3 [2]
4 []
adjacency matrix:
[0, 1, 1, 0, 0]
[1, 0, 1, 0, 0]
[1, 1, 0, 1, 0]
[0, 0, 1, 0, 0]
[0, 0, 0, 0, 0]
list entries stored: 8 which is 2 * E = 8
matrix cells stored: 25 which is V * V
neighbours of vertex 3 from the list, entries read: 1
neighbours of vertex 3 from the matrix, entries read: 5

The output shows the two costs side by side.

The list stores 8 entries. That is 2 times E, because each of the 4 edges is written into two lists, once for each end. The matrix stores 25 cells, which is V times V, no matter how many edges there are.

To find the neighbours of vertex 3, the list version reads 1 entry, the one for vertex 2. The matrix version reads all 5 cells in row 3, because it has to check every possible neighbour to see which ones are 1. The list cost is the number of neighbours of that vertex, which is called its degree. The matrix cost is V, no matter how many neighbours the vertex has.

The cost of a full graph walk

Now run a breadth-first search over a whole graph. The search takes a vertex off the queue, reads its neighbours, and adds unseen neighbours to the queue. Every vertex is taken off the queue at most once, and every edge is looked at once from each end.

With an adjacency list, the cost of a full walk is about V plus E. The V part counts the vertices, because each one is taken off the queue once. The E part counts the neighbour reads: each edge is read from both ends, so the list is read 2 times E in total. We write this as O(V + E).

With an adjacency matrix, the cost is V times V. The search takes each of the V vertices off the queue, and for each one it reads a full row of V cells. We write this as O(V²). The little 2 means V times V.

This program runs the same breadth-first search with both storage forms on random graphs. The random graphs are made with a fixed seed (the starting value of the random number generator), so the numbers do not change from run to run. The search starts at vertex 0.

V, E, list BFS checks, matrix BFS checks, vertices reached
10 15 30 100 10
100 300 600 9900 99
400 1200 2400 160000 400
 
cost of listing the neighbours of one vertex
list entries read: 3
matrix entries read: 400

The list column is 2 times E in each row: 30 for 15 edges, 600 for 300 edges, and 2400 for 1200 edges. The matrix column is V times V: 100, 9,900 and 160,000 for V of 10, 100 and 400. The second row reached 99 of its 100 vertices, because a random graph does not always link every vertex to every other. The matrix still checks 9,900 cells, which is 99 times 100, because each reached vertex reads a full row.

Look at the last row. A graph with 400 vertices and 1,200 edges is sparse. A sparse graph has far fewer edges than the largest possible number of edges, which is V times (V minus 1) divided by 2 for a graph with no repeated edges. For 400 vertices that largest number is 79,800. The graph has only 1,200 of them. For a sparse graph the list form does about 2,400 checks while the matrix form does 160,000. The list form is about 67 times cheaper here, and the gap grows as V grows with E staying small.

A dense graph is one where E is close to the largest possible number, so V and E are about the same size as V squared. In a dense graph the matrix costs about the same as the list, and the matrix is often simpler to read. Most real maps and social graphs are sparse, so the list is the usual choice.

The grid as a graph

A grid can be stored as a graph. Each cell becomes a vertex, and each pair of neighbouring cells becomes an edge. The count of edges is not R times C. It depends on the shape of the grid.

For a grid with R rows and C columns, the number of horizontal edges is R times (C minus 1), because each row has one fewer gap between cells than it has cells. The number of vertical edges is (R minus 1) times C, because each column has one fewer gap than it has cells. The total is R times (C minus 1) plus (R minus 1) times C.

For a 3 by 4 grid, that is 3 times 3 plus 2 times 4, which is 9 plus 8, so 17 edges. For a 10 by 10 grid it is 10 times 9 plus 9 times 10, which is 90 plus 90, so 180 edges. The number of vertices is R times C, which is 12 for the 3 by 4 grid and 100 for the 10 by 10 grid.

This matters because it shows that V and E are both about R times C for a grid. Each cell has at most 4 edges, so E is never more than 2 times V for a grid. A grid is always a sparse graph. That is why a list-style walk, which reads only the neighbours of each cell, is cheap on a grid. The matrix form would store a cell for every pair of cells, which is far more than the grid needs.

When you write the cost of a grid walk, you have two equally correct ways to write it. You can write O(R × C), which uses the grid's own sizes. Or you can write O(V + E), which uses the graph's sizes. Both give the same growth, because V and E are each proportional to R times C. Use the grid form when you are talking about the map. Use the graph form when you are talking about the general algorithm.

Choosing a storage form

The storage form decides which cost you pay. This table summarises the costs for a graph with V vertices and E edges.

Read the table with the variables in mind. The matrix always costs V times V to store, even if the graph has only a few edges. The list costs V plus E to store, so its cost follows the real size of the graph.

In practice most programmers use the list form for graphs and the cell form for grids. A grid does not need a separate list of neighbours for each cell, because the four directions are always the same. The code can compute the neighbour positions by adding 1 or subtracting 1 to the row and column numbers, as the first program in this lesson does.

Common mistakes

Counting the grid as a graph with the wrong size

A common error is to write the cost of a grid walk as O(R + C). The walk must look at every cell, so the true cost is O(R × C). Test your formula with a small grid, such as 3 rows and 4 columns. Count the cells by hand, which gives 12, and check that your formula gives 12 and not 7.

Forgetting that a two-way edge is stored twice

If your graph has links that go both ways, each edge appears in two lists. A program that computes the number of list entries as E instead of 2 times E will undercount the work by half. The code in this lesson printed "list entries stored: 8 which is 2 * E = 8" to make this check visible.

Missing the bounds check

A grid walk must not look outside the grid. If it does, the program raises an error. This is a real message from Python 3.14 when a program reads row 2 of a grid that only has rows 0 and 1:

IndexError: list index out of range

The fix is to check the row and column before you read the cell. The grid_bfs function in this lesson uses 0 <= nr < rows and 0 <= nc < cols for this reason. Put the check before the read, not after it, because Python reads from left to right and stops at the first false part.

Using a matrix when the graph is sparse

A matrix for a graph with 400 vertices always has 160,000 cells, even if the graph has only 1,200 edges. Storing and scanning that matrix costs far more than the list would. If you do not know whether the graph is dense or sparse, look at E first. If E is much smaller than V times V, use the list.

Confusing the number of cells with the number of reached cells

The cost of a search depends on how many cells it reaches. A grid with walls may reach only part of the grid. The wall example reached 6 of the 15 cells. If you give the cost as R times C for a grid that has large walled-off areas, you are giving the worst case, not the cost of this particular run. Say which one you mean.

Practice

Exercise 1

A grid has 50 rows and 80 columns. How many cells does it have? How many neighbour checks does a full breadth-first search make if it checks four directions for each cell, and every cell is reached?

Show the answer

The grid has 50 times 80 cells, which is 4,000 cells. A full search takes each cell off the queue once and checks four directions for each, so it makes 4 times 4,000 neighbour checks, which is 16,000.

Exercise 2

A graph has 6 vertices and 7 edges. Each edge goes both ways. How many entries does the adjacency list store? How many cells does the adjacency matrix store?

Show the answer

The list stores 2 times 7, which is 14 entries, because each undirected edge appears in two lists. The matrix stores 6 times 6, which is 36 cells, whatever the number of edges.

Exercise 3

A graph has 1,000 vertices and 3,000 edges. Compare the cost of a full breadth-first search using the list form with the cost using the matrix form. Give both as formulas and as numbers.

Show the answer

The list form costs about V plus E, which is 1,000 plus 3,000 for the vertex and edge work, or about 4,000 steps. The neighbour reads alone are 2 times E, which is 6,000. The matrix form costs V times V, which is 1,000,000 cell reads. The matrix is about 250 times more work here, because the graph is sparse.

Exercise 4

Write the number of edges in a grid with R rows and C columns, for the case where edges join cells that share a side. Check your formula with a grid of 2 rows and 3 columns by drawing it.

Show the answer

The formula is R times (C minus 1) plus (R minus 1) times C. For 2 rows and 3 columns, that is 2 times 2 plus 1 times 3, which is 4 plus 3, so 7 edges. Drawn out, the 2 by 3 grid has 4 horizontal edges, two in each row, and 3 vertical edges, one in each column, which totals 7.

Exercise 5

A breadth-first search on a grid with walls reaches 40 cells out of 100 cells. Is the cost of this run O(R × C) or smaller? Explain in one or two sentences.

Show the answer

The cost is about the number of cells the search reaches, which is 40 cells and about 160 neighbour checks. The R times C form is the upper limit for any grid, so this run is smaller than the upper limit. Say which one you mean when you report the cost.

Summary

• A grid has R rows and C columns, so it has R times C cells, and a full walk costs about R times C.
• A graph has V vertices and E edges, and a full walk with an adjacency list costs about V plus E.
• An adjacency matrix stores V times V cells and walks in V times V, whatever the number of edges.
• A grid is a sparse graph with at most 4 edges per cell, so a list-style walk is cheap on it.
• The cost of one run depends on how many cells or vertices it reaches, not only on the size of the map.
• Use the list form for sparse graphs, and count each undirected edge twice when you count list entries.

The next lessons in this module cover the cost of big-number arithmetic, and the recurrence trees that describe the cost of recursive algorithms.