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.cs 
using System;
using System.Collections.Generic;
class Program {
	static void Main() {
		int[][] edges = { new int[] {1, 2}, new int[] {1, 3}, new int[] {2, 4}, new int[] {3, 4}, new int[] {4, 5}, new int[] {5, 6} };
		Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
		foreach (int[] e in edges) {
			if (!adj.ContainsKey(e[0])) adj[e[0]] = new List<int>();
			if (!adj.ContainsKey(e[1])) adj[e[1]] = new List<int>();
			adj[e[0]].Add(e[1]);
			adj[e[1]].Add(e[0]);
		}
		List<int> keys = new List<int>(adj.Keys);
		keys.Sort();
		List<string> parts = new List<string>();
		foreach (int v in keys) {
			parts.Add(v + ": [" + string.Join(", ", adj[v]) + "]");
		}
		Console.WriteLine("{" + string.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

  • Dictionary<int, List<int>> maps each int vertex key to a mutable List<int> neighbour list. The ContainsKey checks and indexer writes create each list on first sight of a vertex; those list objects are managed references and their backing arrays are reclaimed by GC.
  • Edge insertion appends both directions with List<int>.Add, so each neighbour list keeps the checked-in edge order visible in the trace. For printing, the code copies adj.Keys to a List<int> and calls Sort() so it does not depend on Dictionary hash-table enumeration order.
adjacency list Each edge adds two directed entries, one in each direction.