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.R 
edges <- list(c(1, 2), c(1, 3), c(2, 4), c(3, 4), c(4, 5), c(5, 6))
adj <- list()
for (e in edges) {
	u <- as.character(e[1])
	v <- as.character(e[2])
	adj[[u]] <- c(adj[[u]], e[2])
	adj[[v]] <- c(adj[[v]], e[1])
}
parts <- character(0)
for (v in 1:6) {
	key <- as.character(v)
	parts[length(parts) + 1] <- paste0(v, ": [", paste(adj[[key]], collapse = ", "), "]")
}
cat("{", paste(parts, collapse = ", "), "}\n", sep = "")

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

  • R: a named list() keyed by character vertex stores neighbour vectors; vertices 1..6 are printed in order.
  • 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.