Graphs and How to Represent Them

Graphs sound advanced and are not. A graph is a tree that is allowed to have loops and more than one route between two points - and that one difference is why every graph algorithm needs a visited set.

The vocabulary you need

• Node (or vertex) - a thing. A person, a page, a city.
• Edge - a connection between two nodes.
• Directed - edges go one way. Twitter follows.
• Undirected - edges go both ways. Facebook friends.
• Weighted - edges carry a cost. Distance, price, time.
• Cycle - a path that returns to where it started.

Adjacency list - the one you will use

A Map from each node to its neighbours. Compact, and fast to walk.

const graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D"]],
  ["C", ["A", "D"]],
  ["D", ["B", "C"]],
])

// From a list of edges, undirected.
function buildGraph(edges) {
  const graph = new Map()

  for (const [from, to] of edges) {
    if (!graph.has(from)) graph.set(from, [])
    if (!graph.has(to)) graph.set(to, [])

    graph.get(from).push(to)
    graph.get(to).push(from)   // drop this line for a directed graph
  }

  return graph
}

console.log(buildGraph([["A", "B"], ["B", "C"]]))

Space is O(nodes + edges). Finding a node's neighbours is O(1). This is the right default.

Adjacency matrix - occasionally

//    A  B  C  D
// A [0, 1, 1, 0]
// B [1, 0, 0, 1]
// C [1, 0, 0, 1]
// D [0, 1, 1, 0]
const matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 1],
  [0, 1, 1, 0],
]

// "Are A and C connected?" is instant.
console.log(matrix[0][2] === 1)  // true

O(1) to check a specific pair, but O(nodes squared) space whether or not the edges exist. On 10,000 nodes that is 100 million cells for a graph that may have only 20,000 edges. Use it only when the graph is small and dense, or you constantly ask about specific pairs.

Graphs that are not called graphs

This is the part worth internalising. All of these are graph problems:

• A grid or maze - each cell is a node, neighbours are up, down, left, right.
• Course prerequisites - a directed graph, and "can I finish?" is cycle detection.
• Word ladders - words are nodes, edges join words one letter apart.
• Dependency resolution - build order is a topological sort.
• Friend suggestions - shortest path of length two.

// Neighbours of a cell — the graph is implicit, no Map needed.
function neighbours(grid, row, col) {
  const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  const out = []

  for (const [dr, dc] of moves) {
    const r = row + dr
    const c = col + dc

    if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
      out.push([r, c])
    }
  }

  return out
}

console.log(neighbours(0, 0))  // the in-bounds neighbours of the corner

You rarely build a Map for a grid - the neighbours are computed from the coordinates. Recognising that a grid is a graph is most of the work.