Graph Representations: Adjacency List vs. Matrix

Dynamic Arrays & Amortized Resizing

Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.

1. Modeling Non-Linear Networks

A Graph $G = (V, E)$ consists of a set of vertices ($V$) connected by edges ($E$). Graphs can be directed (one-way streets) or undirected (two-way friendships), and weighted or unweighted.

2. The Two Standard Graph Representations

Graph:      (0) ───── (1)
             │       /
             │      /
            (2) ── (3)

Adjacency List (Map / Array of Lists):
0: [ 1, 2 ]
1: [ 0, 3 ]
2: [ 0, 3 ]
3: [ 1, 2 ]

Adjacency Matrix (2D Grid):
    0  1  2  3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 0, 1 ]
2 [ 1, 0, 0, 1 ]
3 [ 0, 1, 1, 0 ]

3. Building an Adjacency List

function buildGraph(numVertices, edges) {
  const adjList = new Map();

  for (let i = 0; i < numVertices; i++) {
    adjList.set(i, []);
  }

  for (const [u, v] of edges) {
    adjList.get(u).push(v);
    adjList.get(v).push(u); // Add reverse edge for undirected graph!
  }

  return adjList;
}

const graph = buildGraph(4, [[0, 1], [0, 2], [1, 3], [2, 3]]);
console.log(graph.get(0)); // Output: [1, 2]

4. Tradeoff Comparison Matrix

5. Common Mistakes

• Using Adjacency Matrix for Sparse Graphs: When $V = 100,000$ and $E = 200,000$, an adjacency matrix requires $100,000^2 = 10 ext$ cells ($40 ext$ RAM), crashing instantly! Always default to Adjacency Lists.

6. Next Steps

Use adjacency lists for network representations. Next, let's explore Graph Traversals: BFS & DFS!