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.go 
package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

func main() {
	edges := [][2]int{{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}, {5, 6}}
	adj := map[int][]int{}
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], e[1])
		adj[e[1]] = append(adj[e[1]], e[0])
	}
	keys := []int{}
	for k := range adj {
		keys = append(keys, k)
	}
	sort.Ints(keys)
	parts := []string{}
	for _, v := range keys {
		nbrs := []string{}
		for _, nb := range adj[v] {
			nbrs = append(nbrs, strconv.Itoa(nb))
		}
		parts = append(parts, strconv.Itoa(v)+": ["+strings.Join(nbrs, ", ")+"]")
	}
	fmt.Println("{" + strings.Join(parts, ", ") + "}")
}

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

  • Go: a map[int][]int stores neighbours in edge order; keys are sorted with sort.Ints before printing because Go map iteration 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.