Breadth-first search
Explore a graph in rings of increasing distance with a queue, find shortest paths in unweighted graphs and grids, rebuild the path, and use multi-source BFS.
The algorithm
Put the start in a queue and mark it visited with distance 0. Take the vertex at the front of the queue. For each neighbour not yet visited: mark it visited, set its distance to this vertex’s distance + 1, remember where it came from, and add it at the back of the queue. Repeat until the queue is empty (or until you reach the target).
var adj = new Dictionary<char, char[]>{ ['A'] = new[] { 'B', 'D' }, ['B'] = new[] { 'A', 'C', 'E' }, ['C'] = new[] { 'B', 'E', 'F' }, ['D'] = new[] { 'A', 'E', 'G' }, ['E'] = new[] { 'B', 'C', 'D', 'F', 'G' }, ['F'] = new[] { 'C', 'E', 'G' }, ['G'] = new[] { 'D', 'E', 'F' }}; var (steps, cameFrom) = Bfs(adj, 'A');foreach (var (node, d) in steps) Console.Write($"{node}:{d} ");Console.WriteLine();Console.WriteLine(string.Join(" → ", PathTo(cameFrom, 'F'))); static (Dictionary<char, int>, Dictionary<char, char>) Bfs(Dictionary<char, char[]> adj, char start){ var dist = new Dictionary<char, int> { [start] = 0 }; // doubles as the "visited" set var parent = new Dictionary<char, char>(); var queue = new Queue<char>(); queue.Enqueue(start); while (queue.Count > 0) { char u = queue.Dequeue(); foreach (char v in adj[u]) { if (dist.ContainsKey(v)) continue; // already discovered dist[v] = dist[u] + 1; parent[v] = u; queue.Enqueue(v); } } return (dist, parent);} static List<char> PathTo(Dictionary<char, char> parent, char target){ var path = new List<char> { target }; while (parent.TryGetValue(path[^1], out char p)) path.Add(p); // walk back to the start path.Reverse(); return path;}A:0 B:1 D:1 C:2 E:2 G:2 F:3 A → B → C → F
BFS on a grid
string[] plan ={ "S..#......", "...#..#...", ".#....#.#.", "...#..#..T"};Console.WriteLine(ShortestWalk(plan)); static int ShortestWalk(string[] g){ int rows = g.Length, cols = g[0].Length; var dist = new int[rows, cols]; var queue = new Queue<(int R, int C)>(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { dist[r, c] = -1; // -1 = not visited if (g[r][c] == 'S') { dist[r, c] = 0; queue.Enqueue((r, c)); } } (int Dr, int Dc)[] moves = { (-1, 0), (1, 0), (0, -1), (0, 1) }; while (queue.Count > 0) { var (r, c) = queue.Dequeue(); if (g[r][c] == 'T') return dist[r, c]; foreach (var (dr, dc) in moves) { int nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // off the plan if (g[nr][nc] == '#' || dist[nr, nc] != -1) continue; // blocked or seen dist[nr, nc] = dist[r, c] + 1; queue.Enqueue((nr, nc)); } } return -1; // T cannot be reached}16
Many starting points at once
What BFS is good for
Shortest path when every step costs the same: fewest moves, fewest transfers, fewest hops in a network. Everything within k steps: “people you may know” (friends of friends), all rooms within 3 doors. Flood fill: the “paint bucket” tool, finding all connected cells. Level-by-level processing of trees (level-order traversal is BFS).
# (steel) and . (gap). Count the separate plates: groups of # cells connected up, down, left or right. For the layout below the answer is 4. Use BFS from every # cell you have not visited yet.
Show a hint
#, add 1 to the count and run a BFS from it that marks every # it can reach as visited.
Show the solution
string[] layout ={ "##..#", "#...#", "..#..", "....#"};Console.WriteLine(CountPlates(layout)); static int CountPlates(string[] g){ int rows = g.Length, cols = g[0].Length, count = 0; var seen = new bool[rows, cols]; (int Dr, int Dc)[] moves = { (-1, 0), (1, 0), (0, -1), (0, 1) }; for (int r0 = 0; r0 < rows; r0++) for (int c0 = 0; c0 < cols; c0++) { if (g[r0][c0] != '#' || seen[r0, c0]) continue; count++; // a new plate: flood it var queue = new Queue<(int, int)>(); queue.Enqueue((r0, c0)); seen[r0, c0] = true; while (queue.Count > 0) { var (r, c) = queue.Dequeue(); foreach (var (dr, dc) in moves) { int nr = r + dr, nc = c + dc; if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; if (g[nr][nc] != '#' || seen[nr, nc]) continue; seen[nr, nc] = true; queue.Enqueue((nr, nc)); } } } return count;}4
Remember
BFS uses a queue and explores in rings of increasing distance: O(V + E). In unweighted graphs the first visit is by a shortest path; store parents to rebuild it. Mark vertices visited when you enqueue them. Grids are implicit graphs; multi-source BFS starts from many points at once.