Graphs

Shortest Path (Unweighted, via BFS)

BFS explores a graph layer by layer, so the first time it reaches a vertex is along a shortest path. Track dist[v] and parent[v] while exploring, then walk parents back from the target to reconstruct the route.

Algorithm

On the canonical graph from graph-adjacency-list, the shortest path from 1 to 6 is [1, 2, 4, 5, 6] with distance 4. The path is rebuilt from parent: 6 -> 5 -> 4 -> 2 -> 1, reversed.

layers equal distance BFS order equals distance in an unweighted graph.

Basic Implementation

basic.cs
Replay: real traced execution (multi-file project)
using System;
using System.Collections.Generic;
class Program {
	static void Main() {
		Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
		adj[1] = new List<int> { 2, 3 };
		adj[2] = new List<int> { 1, 4 };
		adj[3] = new List<int> { 1, 4 };
		adj[4] = new List<int> { 2, 3, 5 };
		adj[5] = new List<int> { 4, 6 };
		adj[6] = new List<int> { 5 };
		int src = 1;
		int dst = 6;
		Dictionary<int, int> dist = new Dictionary<int, int>();
		Dictionary<int, int> parent = new Dictionary<int, int>();
		dist[src] = 0;
		parent[src] = 0;
		Queue<int> queue = new Queue<int>();
		queue.Enqueue(src);
		while (queue.Count > 0) {
			int v = queue.Dequeue();
			foreach (int nb in adj[v]) {
				if (!dist.ContainsKey(nb)) {
					dist[nb] = dist[v] + 1;
					parent[nb] = v;
					queue.Enqueue(nb);
				}
			}
		}
		List<int> path = new List<int>();
		int node = dst;
		while (node != 0) {
			path.Add(node);
			node = parent[node];
		}
		path.Reverse();
		Console.WriteLine("[" + string.Join(", ", path) + "]");
		Console.WriteLine(dist[dst]);
	}
}

  1. dist ← {1: 0}

    15Dictionary<int, int> parent = new Dictionary<int, int>();16dist[src] = 0;17parent[src] = 0;
    values this step{1: 0}dist

  2. parent ← {1: null}

    16dist[src] = 0;17parent[src] = 0;18Queue<int> queue = new Queue<int>();
    values this step{1: null}parent

  3. dist ← {1: 0, 2: 1, 3: 1}, parent ← {1: null, 2: 1, 3: 1}, queue ← [2, 3]

    20while (queue.Count > 0) {21	int v = queue.Dequeue();22	foreach (int nb in adj[v]) {
    values this step{1: 0, 2: 1, 3: 1}dist{1: null, 2: 1, 3: 1}parent[2, 3]queue1dequeue

  4. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    20while (queue.Count > 0) {21	int v = queue.Dequeue();22	foreach (int nb in adj[v]) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[3, 4]queue2dequeue

  5. dist ← {1: 0, 2: 1, 3: 1, 4: 2}, parent ← {1: null, 2: 1, 3: 1, 4: 2}

    20while (queue.Count > 0) {21	int v = queue.Dequeue();22	foreach (int nb in adj[v]) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2}dist{1: null, 2: 1, 3: 1, 4: 2}parent[4]queue3dequeue

  6. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4}

    20while (queue.Count > 0) {21	int v = queue.Dequeue();22	foreach (int nb in adj[v]) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4}parent[5]queue4dequeue

  7. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    20while (queue.Count > 0) {21	int v = queue.Dequeue();22	foreach (int nb in adj[v]) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[6]queue5dequeue

  8. dist ← {1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}, parent ← {1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}

    20while (queue.Count > 0) {21	int v = queue.Dequeue();22	foreach (int nb in adj[v]) {
    values this step{1: 0, 2: 1, 3: 1, 4: 2, 5: 3, 6: 4}dist{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent[]queue6dequeue

  9. path ← [1, 2, 4, 5, 6]

    30List<int> path = new List<int>();31int node = dst;32while (node != 0) {
    values this step[1, 2, 4, 5, 6]path{1: null, 2: 1, 3: 1, 4: 2, 5: 4, 6: 5}parent

  10. stdout ← [1, 2, 4, 5, 6]

    36path.Reverse();37Console.WriteLine("[" + string.Join(", ", path) + "]");38Console.WriteLine(dist[dst]);
    values this step[1, 2, 4, 5, 6]stdout[1, 2, 4, 5, 6]path

  11. stdout ← 4

    37	Console.WriteLine("[" + string.Join(", ", path) + "]");38	Console.WriteLine(dist[dst]);39}
    values this step4stdout4dist[6]

  12. BFS path ← 1 -> 2 (1 edge, cost 10), cheaper weighted path ← 1 -> 3 -> 2 (2 edges, cost 2)

    37	Console.WriteLine("[" + string.Join(", ", path) + "]");38	Console.WriteLine(dist[dst]);39}
    values this step1 -> 2 (1 edge, cost 10)BFS path1 -> 3 -> 2 (2 edges, cost 2)cheaper weighted pathuse Dijkstra with a priority queueweighted algorithm1->2 weight 10, 1->3 weight 1, 3->2 weight 1edge weights

Complexity

  • Time: O(V + E)
  • Space: O(V)

Implementation notes

  • The graph is a fixed Dictionary<int, List<int>>; each adj[v] read is a hash-table lookup into a list whose initializer order controls neighbour traversal.
  • There is no separate HashSet<int>. dist.ContainsKey(nb) is the visited check, and dist[nb], parent[nb], then Queue<int>.Enqueue(nb) happen on discovery, so each vertex enters the CLR-managed queue once; these container allocations are reclaimed by GC.
  • parent is a second Dictionary<int, int> with 0 as the source sentinel. Path reconstruction appends to List<int>, follows parent[node], then reverses in place; the replay exposes dist, parent, queue state, and the final [1, 2, 4, 5, 6] path.