codementor on Nostr: Learn: Breadth-first search (BFS) BFS visits the start node, then all its neighbors, ...

Learn: Breadth-first search (BFS)

BFS visits the start node, then all its neighbors, then their neighbors, and so on: rings of growing distance.

It needs a Queue<T> for the nodes to visit and a HashSet<T> for the nodes already seen.

```csharp
var graph = new Dictionary<int, int[]> { [1] = [2, 3], [2] = [4], [3] = [4, 5], [4] = [], [5] = [] };
var seen = new HashSet<int> { 1 };
var queue = new Queue<int>([1]);
var order = new List<int>();
while (queue.TryDequeue(out int n))
{
order.Add(n);
foreach (int next in graph[n]) if (seen.Add(next)) queue.Enqueue(next); // mark when queued
}
Console.WriteLine(string.Join(" ", order));
```

It prints 1 2 3 4 5. Node 4 is reached twice, but queued once.

Cost: O(V + E). Because it goes ring by ring, BFS finds the route with the fewest edges.

#tg001 · TG-001-N