Graph Basics

A small town has seven bus stops, A to G. A bus runs between some pairs of stops and not others: A to B, A to C, B to D, and so on. You want to answer simple questions. Can you get from A to G at all? What is the trip with the fewest stops? If the road between D and F closes, is anyone cut off?

None of the structures so far fits this map. An array has a first item and a last item. A tree has one root, and every node has exactly one parent. The bus map has neither. Stop C connects to three others, and you can ride A, B, D, C and come back to A. You need a structure where anything can connect to anything. That structure is a graph.

#The idea: dots and lines

A graph is a set of things and a set of connections between pairs of them. The things are called nodes (or vertices). The connections are called edges. That is the whole definition. Everything else is vocabulary for describing a particular graph.

The words you will meet in every graph problem:

• Neighbours: the nodes one edge away. C's neighbours are A, D and E.
• Degree: how many edges touch a node. C has degree 3. G has degree 1.
• Path: a sequence of nodes where each pair in a row is joined by an edge, like A, C, E, F, G. Its length is the number of edges: 4.
• Cycle: a path that comes back to where it started without reusing an edge. A, B, D, C, A is one.
• Connected: every node can reach every other. Our map is. If a graph is not, it splits into separate pieces called components. Close the D–F road and the map stays connected, because F is still reachable through E. Close F–G and G becomes a component on its own.

Graphs also come in a few flavours. In an undirected graph an edge works both ways, like a two-way road or a friendship. In a directed graph each edge has an arrow, like a one-way street, a "follows" link, or "task X must happen before task Y". In a weighted graph each edge carries a number, like minutes of travel or a price. This module uses unweighted graphs; weights come later with Dijkstra's algorithm.

A tree is a special kind of graph: connected, with no cycles. That is why the ideas from Tree Traversals carry over. The one new problem is cycles. In a tree you can never walk back to a node you have seen. In a graph you can, so every graph walk needs a way to remember where it has been.

#Storing a graph: the adjacency list

Problems usually hand you a graph as an edge list: a plain list of pairs like [["A","B"], ["A","C"], ...]. That is a poor shape to work with. To find C's neighbours you would scan every edge.

Instead, build an adjacency list: a map from each node to the list of its neighbours. Then "who is next to C?" is one lookup. For an undirected graph, each edge goes into two lists, once in each direction.

for each stop: graph[stop] = []for each edge (u, v):  graph[u].append(v); graph[v].append(u)

// nodes: list of names. edges: list of [u, v] pairs, two-way.
function buildGraph(nodes, edges) {
  const graph = {};
  for (const node of nodes) graph[node] = [];
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u); // leave this line out for a directed graph
  }
  return graph;
}
 
const graph = buildGraph(
  ["A", "B", "C", "D", "E", "F", "G"],
  [["A", "B"], ["A", "C"], ["B", "D"], ["C", "D"],
   ["C", "E"], ["D", "F"], ["E", "F"], ["F", "G"]]
);
graph["C"]; // ["A", "D", "E"]

# nodes: list of names. edges: list of (u, v) pairs, two-way.
def build_graph(nodes, edges):
    graph = {node: [] for node in nodes}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # leave this line out for a directed graph
    return graph
 
graph = build_graph(
    ["A", "B", "C", "D", "E", "F", "G"],
    [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"),
     ("C", "E"), ("D", "F"), ("E", "F"), ("F", "G")],
)
graph["C"]  # ['A', 'D', 'E']

The other classic layout is an adjacency matrix: a V × V table of true/false, where V is the number of nodes, with a mark at row u, column v if there is an edge. It answers "is there an edge between u and v?" in one step. But it always takes V² cells, even when most of them are empty, and listing one node's neighbours means reading a whole row. Most real graphs are sparse (a bus stop has a few neighbours, not thousands), so the adjacency list is the default.

#Grids are graphs too

A maze, a game board, a map of land and water, the pixels of an image: all of these arrive as a 2D grid. Every cell is a node. Its neighbours are the cells directly up, down, left and right of it, as long as they are inside the grid and not a wall.

You do not build an adjacency list for a grid. The neighbours are easy to compute on the spot: add each of four direction offsets to the row and column, and keep the results that land inside the grid on an open cell.

const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // up, down, left, right
 
function gridNeighbours(grid, r, c) {
  const result = [];
  for (const [dr, dc] of DIRS) {
    const nr = r + dr;
    const nc = c + dc;
    const inside = nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length;
    if (inside && grid[nr][nc] !== "#") result.push([nr, nc]);
  }
  return result;
}
 
const grid = ["..#.", "....", "...#"];
gridNeighbours(grid, 1, 1); // [[0, 1], [2, 1], [1, 0], [1, 2]]
gridNeighbours(grid, 0, 3); // [[1, 3]]

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # up, down, left, right
 
def grid_neighbours(grid, r, c):
    result = []
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        inside = 0 <= nr < len(grid) and 0 <= nc < len(grid[0])
        if inside and grid[nr][nc] != "#":
            result.append((nr, nc))
    return result
 
grid = ["..#.", "....", "...#"]
grid_neighbours(grid, 1, 1)  # [(0, 1), (2, 1), (1, 0), (1, 2)]
grid_neighbours(grid, 0, 3)  # [(1, 3)]

A grid with R rows and C columns has R × C nodes and at most 4 edges per node, so it is a sparse graph with O(R × C) nodes and edges. Every graph algorithm in this module works on it unchanged: wherever the code says "for each neighbour", call gridNeighbours.

#Common mistakes

#Check yourself

#What to practise next

Now that you can store a graph, the next step is to walk it. Breadth-First Search answers "what is the fewest-stops trip from A to G?" on this same bus map, and on grids.