Breadth-First Search

From a start vertex, explore the graph layer by layer. Use a queue and a "visited" set. Dequeue a vertex, visit it, enqueue all unvisited neighbours.

Algorithm

Basic Implementation

basic.cs

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 start = 1;
		HashSet<int> visited = new HashSet<int>();
		visited.Add(start);
		Queue<int> queue = new Queue<int>();
		queue.Enqueue(start);
		List<int> order = new List<int>();
		while (queue.Count > 0) {
			int v = queue.Dequeue();
			order.Add(v);
			List<int> neighbours = adj[v];
			for (int i = 0; i < neighbours.Count; i++) {
				int nb = neighbours[i];
				if (!visited.Contains(nb)) {
					visited.Add(nb);
					queue.Enqueue(nb);
				}
			}
		}
		Console.WriteLine("[" + string.Join(", ", order) + "]");
	}
}

BFS uses a queue, so it visits the start vertex, then its neighbours, then the next layer.

Step 1 - Start at 1

The queue starts with [1] and visited starts with {1}.

Step 2 - Visit the first layer

After processing 1, neighbours 2 and 3 are marked and queued.

Step 3 - Deterministic visit order

With insertion-ordered neighbours, BFS visits [1, 2, 3, 4, 5, 6].

Complexity

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

Implementation notes

The graph is a Dictionary<int, List<int>> whose lists are allocated up front with collection initializers. adj[v] is a hash-table lookup, and the fixed fixture means the implementation does not need a missing-key guard.
HashSet<int> is marked before Queue<int>.Enqueue, so a vertex is queued at most once. Both containers manage their backing storage on the CLR heap and are reclaimed by GC.
Neighbours are read by List<int> index in stored order, which is why the replay shows queue states [2, 3], then [3, 4], and the final visit order [1, 2, 3, 4, 5, 6].

queue A `Queue<int>` with `Enqueue` / `Dequeue` implements FIFO without hiding the iteration shape.

visited-before-enqueue Mark a vertex visited before pushing it onto the queue. Keeps the queue size bounded by V.