Graphs

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

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
);

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

  • 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.
adjacency list Each edge adds two directed entries, one in each direction.