Graph Representations

Compare adjacency lists, adjacency matrices, and edge lists for storing graphs in JavaScript, and learn which representation fits each problem's time and space tradeoffs.

5 min read Level 2/5 #dsa#graph#adjacency-list

What you'll learn

Implement adjacency list, adjacency matrix, and edge list in JavaScript
Compare time and space complexity of each representation
Choose the correct structure for sparse vs dense graphs

Every graph algorithm starts by loading the graph into memory. Three structures dominate: adjacency list, adjacency matrix, and edge list. Choosing well determines whether your algorithm fits in memory and runs at the right speed.

Adjacency List

Store a Map from each vertex to its neighbours. This is the default in JavaScript because most real graphs are sparse.

// Unweighted undirected graph: 0-1, 0-2, 1-3, 2-3
function buildAdjList(numVertices, edges) {
  const graph = new Map();
  for (let v = 0; v < numVertices; v++) graph.set(v, new Set());

  for (const [u, v] of edges) {
    graph.get(u).add(v);
    graph.get(v).add(u); // omit for directed
  }
  return graph;
}

const graph = buildAdjList(4, [[0,1],[0,2],[1,3],[2,3]]);
// Map { 0 => Set{1,2}, 1 => Set{0,3}, 2 => Set{0,3}, 3 => Set{1,2} }

For weighted graphs, use Array<{to, weight}> instead of a Set:

function buildWeightedAdjList(numVertices, edges) {
  const graph = new Map();
  for (let v = 0; v < numVertices; v++) graph.set(v, []);

  for (const [u, v, w] of edges) {
    graph.get(u).push({ to: v, weight: w });
    graph.get(v).push({ to: u, weight: w }); // omit for directed
  }
  return graph;
}

Adjacency Matrix

Store a 2-D array where matrix[u][v] holds the edge weight (or 1/0 for unweighted). Best when the graph is dense or you need O(1) edge lookup.

function buildAdjMatrix(numVertices, edges) {
  const matrix = Array.from({ length: numVertices }, () =>
    new Array(numVertices).fill(0)
  );
  for (const [u, v, w = 1] of edges) {
    matrix[u][v] = w;
    matrix[v][u] = w; // omit for directed
  }
  return matrix;
}

Edge List

Simply store every edge as a tuple. The most compact form; used directly by algorithms like Bellman-Ford and Kruskal that iterate over all edges.

const edgeList = [
  [0, 1, 4],
  [0, 2, 1],
  [2, 1, 2],
  [1, 3, 5],
];

Tradeoffs

Operation	Adj List	Adj Matrix	Edge List
Space	O(V+E)	O(V²)	O(E)
Iterate neighbours	O(deg)	O(V)	O(E)
Edge lookup	O(deg)	O(1)	O(E)
Best for	Sparse	Dense	Sorting

For most LeetCode-style problems with sparse graphs, build the adjacency list with Map<number, Set<number>> or Map<number, Array<{to, weight}>> and you will rarely need anything else.

Up Next

With the graph in memory, learn how to traverse it level by level using Breadth-First Search.

Breadth-First Search →