Graphs

Build a Graph as an Adjacency List

Represent an undirected graph as a per-vertex 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.lua 
local edges = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}}
local adj = {}
for _, e in ipairs(edges) do
	local u = e[1]
	local v = e[2]
	if adj[u] == nil then adj[u] = {} end
	if adj[v] == nil then adj[v] = {} end
	adj[u][#adj[u] + 1] = v
	adj[v][#adj[v] + 1] = u
end
io.write("{")
for v = 1, 6 do
	if v > 1 then io.write(", ") end
	io.write(v .. ": [")
	for k = 1, #adj[v] do
		if k > 1 then io.write(", ") end
		io.write(tostring(adj[v][k]))
	end
	io.write("]")
end
io.write("}\n")

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

  • Lua: a table maps each vertex to a sequence of neighbours; vertices 1..6 are printed in order.
  • The replay shows the adjacency list after each edge is added, matching the lesson spec.
adjacency list Each edge adds two directed entries, one in each direction.