Graph representation

Overview

A graph is a set of vertices (nodes) connected by edges. Edges can be directed (one-way, like follows on X) or undirected (two-way, like Facebook friendships), and weighted (distance, cost, time) or unweighted. Trees, grids, linked lists, and state machines are all special graphs.

Before running any graph algorithm, you must choose how to store the graph. An adjacency list (each node maps to its neighbors) is the default for sparse graphs. An adjacency matrix answers 'is there an edge?' in O(1) but uses O(V^2) memory. An edge list is best when you sort edges, as in Kruskal's algorithm.

When to use it

• Input is given as edges, prerequisites, flights, friendships, or connections.
• Relationships between entities matter more than the entities themselves.
• A grid or word transformation can be modeled as nodes with neighbors.
• You need connectivity, paths, cycles, ordering, or spanning trees.

Problem patterns it solves

Where it is used in real software

Key terms

V, E

Number of vertices and edges.

Directed / undirected

One-way edges vs two-way edges.

Weighted

Edges carry a cost such as distance or time.

Degree

Number of edges on a node; in-degree and out-degree for directed graphs.

Sparse / dense

E close to V vs E close to V^2.

Connected component

A maximal group of nodes that are all reachable from each other.

Building an adjacency list

1. 1
   Create an empty list per node

   Array of arrays when nodes are 0..n-1; a Map when node ids are strings.

2. 2
   Add each edge

   graph[u].push(v). For undirected graphs also graph[v].push(u).

3. 3
   Store weights with neighbors

   graph[u].push([v, w]) for weighted graphs.

4. 4
   Track degrees if needed

   indegree[v]++ for topological sort or source detection.

Three representations of the same graph

Undirected edges: 0-1, 0-2, 1-2, 2-3

Adjacency lists are the default because most real graphs are sparse. Use a matrix for dense graphs or algorithms like Floyd-Warshall that read every pair.

Implementation

1// Undirected, nodes 0..n-12function buildGraph(n, edges) {3  const graph = Array.from({ length: n }, () => []);4  for (const [u, v] of edges) {5    graph[u].push(v);6    graph[v].push(u);7  }8  return graph;9}10 11// Directed and weighted with string ids12function buildWeighted(edges) {13  const graph = new Map();14  for (const [from, to, weight] of edges) {15    if (!graph.has(from)) graph.set(from, []);16    if (!graph.has(to)) graph.set(to, []);17    graph.get(from).push([to, weight]);18  }19  return graph;20}21 22// 997. Find the Town Judge with degrees23function findJudge(n, trust) {24  const score = new Array(n + 1).fill(0); // in-degree minus out-degree25  for (const [a, b] of trust) {26    score[a]--;27    score[b]++;28  }29  for (let i = 1; i <= n; i++) if (score[i] === n - 1) return i;30  return -1;31}32 33// 785. Is Graph Bipartite? (graph given as adjacency list)34function isBipartite(graph) {35  const color = new Array(graph.length).fill(-1);36  for (let start = 0; start < graph.length; start++) {37    if (color[start] !== -1) continue;38    color[start] = 0;39    const queue = [start];40    for (let head = 0; head < queue.length; head++) {41      const u = queue[head];42      for (const v of graph[u]) {43        if (color[v] === -1) {44          color[v] = 1 - color[u];45          queue.push(v);46        } else if (color[v] === color[u]) return false;47      }48    }49  }50  return true;51}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Adding only one direction for undirected edges.

  Fix: Push both u -> v and v -> u.

• Assuming nodes are 0-indexed.

  Fix: Many problems use 1..n; allocate n + 1 or subtract 1.

• Missing isolated nodes.

  Fix: Initialize a list for every node, not just nodes that appear in edges.

• Shared inner arrays in JS.

  Fix: Use Array.from({ length: n }, () => []) rather than fill([]).

Interview questions

Practice problems