Graphs

Build a Graph as an Adjacency List

Represent an undirected graph as a map from each vertex to its list of neighbours. For every edge (u, v), append v to adj[u] and u to adj[v]. Neighbour lists keep insertion order so the graph is a stable, deterministic fixture for the search lessons.

Algorithm

Basic Implementation

basic.js 
const edges = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5], [5, 6]];
const adj = new Map();
for (const [u, v] of edges) {
    if (!adj.has(u)) adj.set(u, []);
    if (!adj.has(v)) adj.set(v, []);
    adj.get(u).push(v);
    adj.get(v).push(u);
}
const parts = [];
for (const [v, nbrs] of adj) {
    parts.push(v + ": [" + nbrs.join(", ") + "]");
}
console.log("{" + parts.join(", ") + "}");

The graph fixture is pinned once, then the adjacency list writes each undirected edge in both directions.

Step 1 - Pinned graph fixture

The six vertices and six undirected edges are the shared fixture for BFS and DFS.

Graph with edges (1,2), (1,3), (2,4), (3,4), (4,5), (5,6).123456

Step 2 - Final adjacency list

Each row lists neighbours in the same insertion order used by the lesson.

Adjacency list after all six undirected edges are inserted.vertexneighbours1[2, 3]2[1, 4]3[1, 4]4[2, 3, 5]5[4, 6]6[5]

Complexity

  • Build: O(V + E)
  • Space: O(V + E)

Implementation notes

  • JavaScript: a Map keyed by vertex preserves insertion order, and each entry is an array of neighbours appended in edge order.
  • The replay shows the adjacency map after each edge is added, matching the lesson spec.
adjacency list Each edge adds two directed entries, one in each direction.