Graphs and How to Represent Them

Graphs and How to Represent Them — DSA Tutorial - HTML5ANDCSS3

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"]]))

A grid of connections

javascript

//    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

A grid, as a graph

javascript

// 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
}

The vocabulary you need

Adjacency list - the one you will use

Adjacency matrix - occasionally

Graphs that are not called graphs