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

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.

Basic Implementation

basic.kt

fun main() {
	val edges = listOf(listOf(1, 2), listOf(1, 3), listOf(2, 4), listOf(3, 4), listOf(4, 5), listOf(5, 6))
	val adj = HashMap<Int, MutableList<Int>>()
	for (e in edges) {
		adj.getOrPut(e[0]) { mutableListOf() }.add(e[1])
		adj.getOrPut(e[1]) { mutableListOf() }.add(e[0])
	}
	val parts = mutableListOf<String>()
	for (v in adj.keys.sorted()) {
		parts.add("$v: [" + adj[v]!!.joinToString(", ") + "]")
	}
	println(parts.joinToString(prefix = "{", postfix = "}"))
}

Complexity

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

Implementation notes

Kotlin: a HashMap stores neighbours via getOrPut; keys are sorted before printing because a HashMap is unordered.
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.