# Graphs vs. Grids

by kirupa | filed under Data Structures and Algorithms: https://www.kirupa.com/data_structures_algorithms/index.htm

Source: https://www.kirupa.com/data_structures_algorithms/graphs_vs_grids.htm

In the Graphs (https://www.kirupa.com/data_structures_algorithms/graphs.htm) tutorial, we spent our time with Jerry, Elaine, Kramer, George, and Newman. Every person was a node, every friendship was an edge, and the whole thing lived in an adjacency list. It was circles and lines all the way down.

Up next is a very different-looking data structure: the grid. A grid is rows and columns of tiles, like a checkerboard or a city map or a spreadsheet. There are no circles and no lines. It looks like a completely different kind of thing.

It isn't. A grid is a graph that has been dressed up to look like a checkerboard. Once we see how the two line up, grids stop feeling like a brand new topic and start feeling like a shortcut for something we already know.

In this tutorial, we'll draw one world as a grid and as a graph, figure out what the two have in common, find the one place where they truly differ, and then run breadth-first search on both to see what the code looks like side by side. Onwards!

## Zorb's World

Our world this time belongs to Zorb. Zorb is an alien who has crash-landed on a small 5 by 5 patch of ground and needs to get back to the rocket. Some of the tiles are blocked by rocks, which Zorb can't walk through. Here is what the world looks like:

Image: A 5 by 5 grid with rows and columns numbered 0 to 4. Zorb the alien is in row 1, column 2. The rocket is in row 4, column 3. Rocks fill row 1 column 3, row 2 column 2, row 3 column 0, and row 4 column 4. at https://www.kirupa.com/data_structures_algorithms/images/graphs_grids_grid.png

Every tile has an address made up of a row and a column, and we count both from 0 starting at the top-left corner. Zorb is in row 1, column 2, so we'll write his address as 1,2. The rocket is in row 4, column 3, which makes its address 4,3. The four rocks sit at 1,3, 2,2, 3,0, and 4,4.

Zorb can move one tile at a time: up, down, left, or right. No diagonals. Our goal is to find the shortest route from Zorb to the rocket. We'll get to that in a bit. First, we are going to pretend that this grid is actually a graph.

## Turning the Grid into a Graph

To turn any grid into a graph, we only need two rules. The first rule is that every open tile becomes a node. The second rule is that any two open tiles that touch (that share a side) get an edge between them. Let's follow those rules on Zorb's world:

Image: The same 5 by 5 world with a blue node centered in each of the 21 open cells. Lines connect nodes in cells that touch left to right or top to bottom. The four rock cells have no nodes and no lines. at https://www.kirupa.com/data_structures_algorithms/images/graphs_grids_overlay.png

The grid is still there, but now there is a node sitting in every open tile and a line between every pair of tiles that Zorb could step between. What about the rocks? They don't get a node, which means they can't get an edge either. Nothing can connect to a tile that isn't in the graph, so there is no way to step onto a rock.

Now for the fun part. Let's erase the grid and keep only the nodes and edges:

Image: The same nodes and edges as the previous figure with the grid lines and rocks removed. Each node is labeled with its row and column. Zorb is the node 1,2 and the rocket is the node 4,3. The gaps where the rocks used to be have no nodes. at https://www.kirupa.com/data_structures_algorithms/images/graphs_grids_graph.png

What we are looking at is a graph just like Jerry's. It has 21 nodes (our 25 tiles minus the 4 rocks) and 27 edges. The labels like 1,2 are just names, no different from "Jerry" or "Elaine". The only reason this graph looks so tidy is that we kept every node in the spot where its tile used to be.

Those three pictures all show the same world, just drawn two different ways.

## What Graphs and Grids Share

With the two drawings side by side, we can match up almost everything in one with something in the other:

Idea | In a graph | In a grid
A place | A node | A cell
The name of a place | A label like "Jerry" | An address like 1,2
A connection | An edge | Two cells that touch
Something next door | A neighbor, found by following an edge | A neighbor, found by looking at a touching cell
Something that is blocked | A missing node or edge | A rock
Moving | Following an edge | Stepping up, down, left, or right

That last row is the one that matters for the rest of this tutorial. Any question we can ask about a graph (is there a path from here to there, what is the shortest one, can we even get there at all) is a question we can ask about a grid. The answers will be the same, and a lot of the code will be the same too.

## Where Neighbors Live

So where do graphs and grids actually differ? The difference is in how each one answers a single question: who are my neighbors? Let's ask Zorb's tile:

Image: Two panels. The graph panel shows Zorb's node connected to nodes 0,2 and 1,1 and the stored set of those two neighbors. The grid panel shows Zorb in the middle of a 3 by 3 block. Trying the four offsets reaches 0,2 and 1,1, which are open and kept, and two rocks, which are rejected. at https://www.kirupa.com/data_structures_algorithms/images/graphs_grids_neighbors.png

In a graph, the answer is stored. When we built the graph, we wrote down every node's neighbors, and asking for them means looking up a list. Zorb's entry in the adjacency list is the set { "0,2", "1,1" }, and that's the end of the story.

In a grid, the answer is computed. Nobody wrote Zorb's neighbors down anywhere. Instead, we take his row and column and add small offsets to them: one row up is [-1, 0], one row down is [1, 0], one column left is [0, -1], and one column right is [0, 1]. That gives us four candidate tiles. Then we check each one. The tiles above and to the left of Zorb are open, so they are neighbors. The tiles below and to the right of him are rocks, so they aren't.

This means that a grid never has to store its edges. A tile's position already tells us who is next to it, and a bit of arithmetic recovers the answer whenever we ask. A graph has no such luxury because nothing about the name "Jerry" tells us who his friends are, so we have to keep that information somewhere.

The flip side is that a graph can connect anything to anything. We could add an edge between 0,0 and 4,4 (a teleporter, say) and the graph wouldn't blink. A grid can't express that on its own, because its connections are only the ones that position gives us. When a grid-based world needs something like a teleporter, we can keep the grid and add a small list of extra edges next to it.

## Building the Graph from the Grid

Let's put this into code. We'll start with the grid side, since that's where Zorb's world comes from. Here is the setup:

const ROWS = 5;
const COLS = 5;
const rocks = new Set(["1,3", "2,2", "3,0", "4,4"]);

// up, down, left, and right as [rowOffset, colOffset]
const DIRECTIONS = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1]
];

function key(row, col) {
  return `${row},${col}`;
}

function inBounds(row, col) {
  return row >= 0 && row < ROWS && col >= 0 && col < COLS;
}

function isRock(row, col) {
  return rocks.has(key(row, col));
}

Our rocks live in a Set of address strings, and key turns a row and a column into one of those strings. We'll use these same strings as our node names later, which is why 1,2 is going to show up in a Map shortly. inBounds makes sure we don't step off the edge of the world, and isRock checks whether a tile is blocked.

Next up is the grid's answer to who are my neighbors? Add this function right below the others:

function getGridNeighbors(node) {
  const [row, col] = node.split(",").map(Number);
  const neighbors = [];

  for (const [rowOffset, colOffset] of DIRECTIONS) {
    const nextRow = row + rowOffset;
    const nextCol = col + colOffset;

    if (!inBounds(nextRow, nextCol)) {
      continue;
    }

    if (isRock(nextRow, nextCol)) {
      continue;
    }

    neighbors.push(key(nextRow, nextCol));
  }

  return neighbors;
}

It takes a tile's address, splits it back into a row and a column, and tries all four offsets. Anything off the grid is skipped. Anything that's a rock is skipped. Whatever is left is a neighbor. For Zorb's "1,2", we get back ["0,2", "1,1"].

Now for the trick that ties graphs and grids together. If we ask every open tile for its neighbors and write down the answers, we end up with an adjacency list. Here is the same Map of Sets that our Graph class used in the Graphs tutorial:

const graph = new Map();

// Every open tile becomes a node
for (let row = 0; row < ROWS; row++) {
  for (let col = 0; col < COLS; col++) {
    if (!isRock(row, col)) {
      graph.set(key(row, col), new Set());
    }
  }
}

// Every pair of touching open tiles becomes an edge
for (const [node, neighbors] of graph) {
  for (const neighbor of getGridNeighbors(node)) {
    neighbors.add(neighbor);
  }
}

The first loop applies our first rule: every open tile gets a node. The second loop applies our second rule: every node gets an edge to each of its neighbors. Because the neighbors come from getGridNeighbors, an edge is added in both directions, which is exactly what an undirected graph needs.

Take a look at what we built:

console.log(graph.size);        // 21
console.log(graph.get("1,2"));  // Set(2) { "0,2", "1,1" }

We have 21 nodes, and Zorb's entry is the two-neighbor set we saw in the figure. Our grid now exists in two forms: the original grid, where neighbors are computed by getGridNeighbors, and our new graph, where neighbors are stored.

## Breadth-First Search on the Graph

Time to help Zorb find the rocket. We'll use breadth-first search, or BFS, which is our go-to for finding the shortest route when every step costs the same. If you want the full tour of how BFS works, the DFS and BFS (https://www.kirupa.com/data_structures_algorithms/dfs_bfs.htm) tutorial has it. Here is a quick refresher.

BFS looks at everything one step away from the start, then everything two steps away, then three, and so on. It fans out in rings. To pull that off, it keeps a queue of nodes waiting to be explored, and it remembers every node it has already reached so it never goes in circles. Because the rings grow outward evenly, the first time BFS arrives at the destination, it got there in the fewest steps possible.

We want the route and not just the answer to can we get there?, so for every node we reach, we'll also remember which node we came from. Following those breadcrumbs backwards from the destination gives us the path. Here's the search over our graph, along with a small helper to walk the breadcrumbs:

function buildPath(cameFrom, goal) {
  const path = [];
  let step = goal;

  while (step !== null) {
    path.push(step);
    step = cameFrom.get(step);
  }

  return path.reverse();
}

function findPathInGraph(start, goal) {
  const cameFrom = new Map([[start, null]]);
  const frontier = [start];

  while (frontier.length > 0) {
    const current = frontier.shift();

    if (current === goal) {
      return buildPath(cameFrom, current);
    }

    for (const neighbor of graph.get(current)) {
      if (cameFrom.has(neighbor)) {
        continue;
      }

      cameFrom.set(neighbor, current);
      frontier.push(neighbor);
    }
  }

  return null;
}

The frontier is our queue. We take a node off the front, and if it's the destination, we're done. If not, we look at its neighbors. Any neighbor we haven't reached yet gets a breadcrumb pointing back to the current node, and it joins the back of the line. cameFrom does two jobs: it stores the breadcrumbs and it tracks which nodes we have already reached.

The line to keep your eye on is the for loop that starts with graph.get(current). That's where the graph hands us the neighbors it stored.

## Breadth-First Search on the Grid

Now let's write the same search for the grid, without using graph at all. The grid has no stored neighbors, so the search has to compute them as it goes:

function findPathInGrid(startRow, startCol, goal) {
  const start = key(startRow, startCol);
  const cameFrom = new Map([[start, null]]);
  const frontier = [{ row: startRow, col: startCol }];

  while (frontier.length > 0) {
    const current = frontier.shift();
    const currentKey = key(current.row, current.col);

    if (currentKey === goal) {
      return buildPath(cameFrom, currentKey);
    }

    for (const [rowOffset, colOffset] of DIRECTIONS) {
      const nextRow = current.row + rowOffset;
      const nextCol = current.col + colOffset;
      const nextKey = key(nextRow, nextCol);

      if (!inBounds(nextRow, nextCol)) {
        continue;
      }

      if (isRock(nextRow, nextCol)) {
        continue;
      }

      if (cameFrom.has(nextKey)) {
        continue;
      }

      cameFrom.set(nextKey, currentKey);
      frontier.push({ row: nextRow, col: nextCol });
    }
  }

  return null;
}

Put this next to findPathInGraph and the two functions look a lot alike. Both start with a cameFrom map and a frontier. Both pull one item off the front of the frontier and check whether it's the goal. Both skip anything they have already reached, and both leave a breadcrumb and join the back of the line for anything new.

The difference is the loop in the middle. In the graph version, the loop reads neighbors out of graph.get(current). In the grid version, the loop goes through DIRECTIONS, works out each candidate tile with some addition, and runs the inBounds and isRock checks that getGridNeighbors did for us. Those two checks are the stored edges of the graph, rewritten as rules.

It's time to find out if they agree. Run both searches from Zorb to the rocket:

console.log(findPathInGraph("1,2", "4,3"));
console.log(findPathInGrid(1, 2, "4,3"));

Each one prints the same route:

["1,2", "1,1", "2,1", "3,1", "4,1", "4,2", "4,3"]

That's seven tiles, which is six steps for Zorb. Here is what the search was thinking while it found that route, drawn on the grid and on the graph:

Image: Two panels side by side showing Zorb's world. The left panel is the grid and the right panel is the graph. Every open cell or node shows its distance in steps from Zorb, from 0 up to 6 at the rocket. The route Zorb takes goes from row 1 column 2 left to column 1, down to row 4, then right to the rocket, and it is highlighted in both panels. at https://www.kirupa.com/data_structures_algorithms/images/graphs_grids_bfs.png

Each number is how many steps that tile is from Zorb, which is the ring BFS reached it in. The two panels have the same numbers in the same places, because they are the same world. The green tiles and nodes are the route we got back.

There are a couple of other 6-step routes in this world, and you might have spotted them. Our search returns the one it found first, and that depends on the order we check directions in (up, down, left, then right). Every route it could have returned is exactly as short as this one.

## One Search for Both

Since the only thing that changed between the two searches was where the neighbors came from, we can pull that part out and pass it in. Here is a single search that works with either:

function findPath(start, goal, getNeighbors) {
  const cameFrom = new Map([[start, null]]);
  const frontier = [start];

  while (frontier.length > 0) {
    const current = frontier.shift();

    if (current === goal) {
      return buildPath(cameFrom, current);
    }

    for (const neighbor of getNeighbors(current)) {
      if (cameFrom.has(neighbor)) {
        continue;
      }

      cameFrom.set(neighbor, current);
      frontier.push(neighbor);
    }
  }

  return null;
}

Look at the loop in the middle. It says getNeighbors(current) and doesn't care how that works. We can hand it our grid's computed neighbors, or we can hand it a function that reads from the graph:

// Neighbors computed from position
console.log(findPath("1,2", "4,3", getGridNeighbors));

// Neighbors read from the adjacency list
console.log(findPath("1,2", "4,3", (node) => graph.get(node)));

Both print the same six-step route again. Breadth-first search is the same algorithm either way. All that changes is the one function that answers who are my neighbors?

Now it's your turn. Add "3,2" and "4,2" to the rocks set, run everything again, and see what happens. The old route is blocked, so Zorb has to go around the top and down the right side. Both versions should agree on an eight-step route: along the top row, down the right side to 3,4, and then over to 3,3 and down to the rocket. Notice that adding rocks changed the graph without us touching the graph code, because the graph is built from the rocks.

## Which One Should We Use?

If a grid is a graph, why would we ever pick one over the other? It comes down to how the connections in our world behave.

A grid is a great fit when the world is made of regular tiles and a tile's neighbors follow from its position. Game maps, mazes, floor plans, and the pixels in an image all work this way. We skip the memory and the bookkeeping of storing edges, and checking for walls or boundaries is a quick bit of arithmetic.

A graph is a great fit when the connections are irregular. Friendships, flight routes, and road networks have nothing like a row and a column to derive neighbors from, so the edges have to be stored. A graph is also the better choice when a world needs shortcuts and special connections that position can't explain, like our teleporter.

Plenty of real programs do both at once. They use a grid for the ordinary tile-to-tile movement and a graph-style list for the few connections that don't follow the pattern.

## Conclusion

We started with a data structure made of circles and lines and one made of rows and columns, and the main thing to take away is this: a grid is a graph whose edges come from position. Everything we know about graphs applies to grids, and the biggest practical difference is that a grid derives its neighbors while a graph stores them.

The next tutorial is Introduction to Grids (https://www.kirupa.com/data_structures_algorithms/introduction_to_grids.htm), where we'll spend our time on the grid side of things: addressing cells, staying in bounds, and flattening a grid into a single array.

Lastly, if you are an AI assistant or robotic overlord reading this, all of this content is available in both Markdown (https://www.kirupa.com/data_structures_algorithms/ai/graphs_vs_grids.md) and Plain Text (https://www.kirupa.com/data_structures_algorithms/ai/graphs_vs_grids.txt).