Breadth-first traversal

10 min guided lesson · Read, predict, then run

Breadth-first traversal follows layers from one start

Breadth-first traversal explores reachable nodes in increasing edge distance from its starting node when edges are unweighted. A queue keeps discovered work in arrival order, while a seen set prevents repeated discovery. The sample returns only the visit order, not an explicit distance or route map. Reachability from A is the contract shown: disconnected nodes elsewhere in the dictionary would not automatically be included. Before tracing the loop, read every listed edge as a directed connection rather than assuming each connection works in both directions.

A graph connects A to B and C, B to D, and C to E. A FIFO queue visits A, B, C, D, E in levels. — With B before C in A's adjacency list, the FIFO queue explores each level before the next.

Trace the queue through the shared destination

A is queued and marked seen first. Removing A records it and queues B then C. Removing B discovers D, leaving C then D pending. Removing C finds D already seen, so it does not queue D again. Finally D is removed and has no neighbors. The resulting order is A,B,C,D. The shared edge destination is the important test: D has two incoming routes, but the seen check ensures one recorded visit. Queue order, not dictionary-key enumeration, controls this particular traversal.

foreach (var next in graph[node]) if (seen.Add(next)) queue.Enqueue(next);

Mark discovery before another node can repeat it

Seen.Add returns true only when a node is first added. The code marks a neighbor at enqueue time, so another processed node cannot queue the same neighbor as new work. Marking only when dequeuing could create duplicate pending entries. The invariant is that every queued node is already marked discovered, while order contains nodes whose queued work has actually been processed. Keeping those stages distinct makes both the shared-D case and a possible cycle back to A easy to reason about.

Traversal order depends on neighbor order

B appears before C because A’s neighbor array lists B first. Reversing that array can change the valid breadth-first order while preserving layer distances. A program requiring one reproducible report must establish a neighbor ordering policy instead of assuming every collection has a suitable stable order. The dictionary lookup also assumes every referenced neighbor has a declared adjacency entry. An unknown key can fail when its turn is processed, so validate that shape if graph data comes from outside the trusted example.

Practice: add cycles and disconnected nodes

Add an edge from D back to A and predict that the displayed baseline order remains unchanged because A is already seen. Then add an isolated E entry without connecting it to A, and explain why E is not visited. In a separate experiment, reverse A’s neighbors to C then B and predict A,C,B,D. These changes isolate cycle prevention, starting-component scope, and tie ordering; they should not be combined into one edit before each effect is understood.

Write the queue and seen set after each removal, not only the final printed order.
A self-loop and a shared destination should not cause repeated processing of an already discovered node.

Practice: store the result the caller actually needs

For an independent extension, maintain a distance dictionary when a neighbor is first discovered. Predict A zero, B one, C one, and D two for the original graph. Add a predecessor map and reconstruct one route to D, observing that the first listed shortest route wins under the neighbor order. This does not turn the base output into a weighted shortest-path solver. Weighted edges require a different algorithm or a separately justified special case, not merely another integer stored beside a queue entry.

Distinguish the visit-order list, minimum unweighted edge counts, and a chosen predecessor route as separate outputs.
If all graph components must be covered, start additional traversals from still-unseen nodes under an explicit outer policy.

Check discovery, processing, and graph assumptions

A correct explanation accounts for every reachable node and every scanned outgoing edge without inventing repeated visits for shared destinations. With ordinary efficient set and dictionary operations, work grows with the reachable vertices and their edges, while stored state tracks discovered and pending nodes. The local arrays, queue, and set are managed features supported by this runtime. Keep the result contract precise: this program prints one deterministic order for its listed adjacency arrays, rather than returning every component, weighted distances, or all possible shortest routes.

Baseline order is A,B,C,D, with D recorded once despite two incoming edges.
Discovery is marked at enqueue time through seen.Add.
Neighbor order, directed-edge interpretation, complete adjacency entries, and the chosen start are part of the traversal contract.

A working example

using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Threading;
using System.Threading.Tasks;

var graph = new Dictionary<string, string[]> { ["A"] = new[] { "B", "C" }, ["B"] = new[] { "D" }, ["C"] = new[] { "D" }, ["D"] = Array.Empty<string>() };
var queue = new Queue<string>(); var seen = new HashSet<string>();
queue.Enqueue("A"); seen.Add("A");
var order = new List<string>();
while (queue.Count > 0)
{
    var node = queue.Dequeue(); order.Add(node);
    foreach (var next in graph[node]) if (seen.Add(next)) queue.Enqueue(next);
}
Console.WriteLine(string.Join(",", order));

Open in playground

Expected output

A,B,C,D

Try this
Mark a node when enqueuing it so another neighbor cannot enqueue it again.

Breadth-first traversal