Build a Graph as an Adjacency List

Represent an undirected graph as a per-vertex list of neighbours. For every edge (u, v), record v as a neighbour of u and u as a neighbour of v. Neighbour lists keep insertion order so the graph is a stable, deterministic fixture for the search lessons.

Algorithm

The canonical fixture is 6 vertices [1..6] with undirected edges (1,2), (1,3), (2,4), (3,4), (4,5), (5,6) inserted in that order. The final adjacency list is {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3, 5], 5: [4, 6], 6: [5]}. This same graph drives graph-bfs, graph-dfs, and graph-shortest-path-bfs.

adjacency list Each edge adds two directed entries, one in each direction.

Visual walkthrough

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.

Step 2 - Final adjacency list

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

Basic Implementation

                            basic.sql
                        

                            .mode list
.headers off
CREATE TABLE edge(u INTEGER, v INTEGER);
INSERT INTO edge(u, v) VALUES
  (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (5, 6);

-- Expand each undirected edge into two directed rows, keeping an order key
-- so neighbour lists stay in insertion order.
WITH directed(node, nbr, seq) AS (
  SELECT u, v, rowid * 2 - 1 FROM edge
  UNION ALL
  SELECT v, u, rowid * 2 FROM edge
)
SELECT '{' || GROUP_CONCAT(entry, ', ') || '}'
FROM (
  SELECT node, node || ': [' || GROUP_CONCAT(nbr, ', ') || ']' AS entry
  FROM (SELECT node, nbr FROM directed ORDER BY node, seq)
  GROUP BY node
  ORDER BY node
);

                        

Complexity

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

Implementation notes

SQL: each undirected edge expands into two directed rows with an order key, then GROUP_CONCAT builds each vertex's neighbour list (a CLI script run with sqlite3).
The replay shows the adjacency list as the edges are processed, matching the lesson spec.