What is graph traversal? Explain breadth-first search (BFS) with a C# implementation, why it finds the shortest path in an unweighted graph, and where you would use it in a real system.

1. Representing the graph

2. Mark visited when you enqueue, not when you dequeue

Wrong: mark on dequeue
  A -> B, C; B -> D; C -> D
  D is enqueued twice (from B and C) before either copy is processed
  In dense graphs the queue can hold O(E) entries instead of O(V)

Right: mark on enqueue
  if visited.Add(neighbour) then queue.Enqueue(neighbour)

HashSet<T>.Add returns false if already present, so one call both checks and marks.

3. Levels and depth limits

Process the queue one layer at a time to know the distance without storing it per node:

int depth = 0;
while (queue.Count > 0 && depth <= maxDepth)
{
    int layerSize = queue.Count;
    for (int i = 0; i < layerSize; i++) { var node = queue.Dequeue(); /* ... */ }
    depth++;
}

4. Multi-source BFS

Start with all sources in the queue at distance 0. Each node's distance becomes the distance to its nearest source. Example: distance from every store to the nearest warehouse in one pass, O(V + E), instead of one BFS per store.

5. Bidirectional BFS

Search from both ends and stop when the frontiers meet. With branching factor b and distance d, this explores about 2 × b^(d/2) nodes instead of b^d. For social graphs (b ≈ 200, d = 6) that is the difference between feasible and impossible.

from start:  layer1  layer2  layer3
                                    \  meet
from goal :  layer1  layer2  layer3 /

6. Memory and big graphs

BFS memory is the widest layer. In a social graph, layer 3 can contain millions of nodes. Options: depth limits, bidirectional BFS, or a graph database (Neo4j, Azure Cosmos DB Gremlin, SQL Server graph tables, PostgreSQL recursive CTEs) that traverses near the data. A recursive CTE in SQL is effectively BFS by level:

WITH RECURSIVE downstream(service, depth) AS (
    SELECT callee, 1 FROM calls WHERE caller = 'billing'
    UNION
    SELECT c.callee, d.depth + 1
    FROM calls c JOIN downstream d ON c.caller = d.service
    WHERE d.depth < 3
)
SELECT service, MIN(depth) FROM downstream GROUP BY service;

(SQL Server uses WITH without RECURSIVE, and UNION ALL, so add a depth limit to stop cycles.)

7. Try it yourself

Shortest moves for a knight on a chessboard is a classic BFS on an implicit graph:

static int KnightMoves((int r, int c) from, (int r, int c) to)
{
    var moves = new (int, int)[] { (1,2),(2,1),(-1,2),(-2,1),(1,-2),(2,-1),(-1,-2),(-2,-1) };
    var dist = new Dictionary<(int, int), int> { [from] = 0 };
    var q = new Queue<(int r, int c)>();
    q.Enqueue(from);
    while (q.Count > 0)
    {
        var cur = q.Dequeue();
        if (cur == to) return dist[cur];
        foreach (var (dr, dc) in moves)
        {
            var next = (cur.r + dr, cur.c + dc);
            if (next.Item1 is < 0 or > 7 || next.Item2 is < 0 or > 7 || dist.ContainsKey(next)) continue;
            dist[next] = dist[cur] + 1;
            q.Enqueue(next);
        }
    }
    return -1;
}
Console.WriteLine(KnightMoves((0, 0), (7, 7))); // 6

public static class Bfs
{
    // Shortest path (fewest edges) from start to goal; null if unreachable.
    public static List<T>? ShortestPath<T>(IReadOnlyDictionary<T, List<T>> graph, T start, T goal)
        where T : notnull
    {
        var parent = new Dictionary<T, T>();
        var visited = new HashSet<T> { start };
        var queue = new Queue<T>();
        queue.Enqueue(start);

        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            if (EqualityComparer<T>.Default.Equals(node, goal))
                return Rebuild(parent, start, goal);

            if (!graph.TryGetValue(node, out var neighbours)) continue;
            foreach (var next in neighbours)
                if (visited.Add(next))           // mark on enqueue
                {
                    parent[next] = node;
                    queue.Enqueue(next);
                }
        }
        return null;
    }

    private static List<T> Rebuild<T>(Dictionary<T, T> parent, T start, T goal) where T : notnull
    {
        var path = new List<T> { goal };
        for (var n = goal; !EqualityComparer<T>.Default.Equals(n, start); n = parent[n])
            path.Add(parent[n]);
        path.Reverse();
        return path;
    }

    // Everything within maxDepth hops, with its distance (impact analysis)
    public static Dictionary<T, int> WithinHops<T>(IReadOnlyDictionary<T, List<T>> graph, T start, int maxDepth)
        where T : notnull
    {
        var dist = new Dictionary<T, int> { [start] = 0 };
        var queue = new Queue<T>();
        queue.Enqueue(start);
        while (queue.Count > 0)
        {
            var node = queue.Dequeue();
            if (dist[node] == maxDepth || !graph.TryGetValue(node, out var neighbours)) continue;
            foreach (var next in neighbours)
                if (dist.TryAdd(next, dist[node] + 1))
                    queue.Enqueue(next);
        }
        return dist;
    }
}

// Usage: which services are affected within 3 hops if "billing" changes?
// Reverse the "caller -> callee" edges so we walk from billing to its callers.
var callersOf = calls.GroupBy(c => c.Callee).ToDictionary(g => g.Key, g => g.Select(c => c.Caller).ToList());
var impacted = Bfs.WithinHops(callersOf, "billing", 3);