Graph Traversal in C#: BFS, DFS and Topological Sort

Graph problems in C# have a specific failure mode, and it happens before any algorithm runs. It is in how the graph was stored.

Every program below is complete, was run on .NET 10, and its output is pasted from the run.

Pattern 31 — How the graph is stored

List<List<int>> is what most C# solutions use. It is readable and it is correct. It also allocates one List object per node, each with its own backing array, scattered across the heap. At 200,000 nodes that is 200,000 objects to allocate, and every neighbour lookup is a pointer chase to somewhere else in memory.

The alternative is compressed sparse row: the whole graph in two flat arrays.

int n = 5;
(int u, int v)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)];

// The version most C# solutions use: n List objects, each with its own array.
List<List<int>> adj = [];
for (int i = 0; i < n; i++) adj.Add([]);
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }

Console.WriteLine("List<List<int>>:");
for (int i = 0; i < n; i++) Console.WriteLine($"  {i}: [{string.Join(", ", adj[i])}]");
Console.WriteLine($"  objects allocated: 1 outer list + {n} inner lists + their backing arrays");

// Compressed sparse row: two arrays, total, for the whole graph.
int[] head = new int[n + 1];
foreach (var (u, v) in edges) { head[u + 1]++; head[v + 1]++; }   // degree, offset by one
for (int i = 0; i < n; i++) head[i + 1] += head[i];               // prefix sum -> start offsets

int[] next = new int[edges.Length * 2];
int[] cursor = (int[])head.Clone();
foreach (var (u, v) in edges)
{
    next[cursor[u]++] = v;
    next[cursor[v]++] = u;
}

Console.WriteLine($"\nCSR:");
Console.WriteLine($"  head = [{string.Join(", ", head)}]");
Console.WriteLine($"  next = [{string.Join(", ", next)}]");
Console.WriteLine($"  objects allocated: 2 arrays, whatever the size of the graph");

Console.WriteLine("\nneighbours of each node, read from CSR:");
for (int u = 0; u < n; u++)
{
    var nb = new List<int>();
    for (int e = head[u]; e < head[u + 1]; e++) nb.Add(next[e]);
    Console.WriteLine($"  {u}: [{string.Join(", ", nb)}]   (same: {nb.OrderBy(x => x).SequenceEqual(adj[u].OrderBy(x => x))})");
}

It prints:

List<List<int>>:
  0: [1, 2]
  1: [0, 3]
  2: [0, 3]
  3: [1, 2, 4]
  4: [3]
  objects allocated: 1 outer list + 5 inner lists + their backing arrays

CSR:
  head = [0, 2, 4, 6, 9, 10]
  next = [1, 2, 0, 3, 0, 3, 1, 2, 4, 3]
  objects allocated: 2 arrays, whatever the size of the graph

neighbours of each node, read from CSR:
  0: [1, 2]   (same: True)
  1: [0, 3]   (same: True)
  2: [0, 3]   (same: True)
  3: [1, 2, 4]   (same: True)
  4: [3]   (same: True)

Look at how head is built. Count each node’s degree into head[u+1], then take a prefix sum — the same trick as part 3, used here to turn degrees into starting offsets. cursor is a copy that gets consumed while filling, so each node’s run is written in order.

Neighbours of u are next[head[u] .. head[u+1] - 1]. head has n+1 cells so head[u+1] always exists for the last node — the same off-by-one discipline as the prefix sum array.

Is it worth it? Not for a 5-node graph, and not when the code has to be read by someone else. It is worth it when n is in the hundreds of thousands, and it is the difference between a solution that passes and one that does not.

Reach for it when the graph is big and static. If you are adding edges as you go, keep the lists.

Pattern 32 — BFS for shortest paths

On an unweighted graph, breadth-first search gives shortest paths, and it does so without ever comparing two distances.

The reason is the queue. It holds an entire layer before it holds anything from the next one, so the first time a node is reached, it is reached by a shortest path. There is never a shorter one to find later.

int n = 7;
(int, int)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 6)];

List<int>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }

int start = 0, goal = 5;

int[] dist = new int[n];
int[] parent = new int[n];
Array.Fill(dist, -1);
Array.Fill(parent, -1);

Queue<int> q = [];
q.Enqueue(start);
dist[start] = 0;

while (q.Count > 0)
{
    int u = q.Dequeue();
    Console.WriteLine($"visit {u} (distance {dist[u]})");
    foreach (int v in adj[u])
    {
        if (dist[v] != -1) continue;          // already has its shortest distance
        dist[v] = dist[u] + 1;
        parent[v] = u;
        q.Enqueue(v);
        Console.WriteLine($"      -> {v} first reached, distance {dist[v]}");
    }
}

List<int> path = [];
for (int at = goal; at != -1; at = parent[at]) path.Add(at);
path.Reverse();

Console.WriteLine($"\ndistances: [{string.Join(", ", dist)}]");
Console.WriteLine($"path {start} -> {goal}: {string.Join(" -> ", path)}  (length {dist[goal]})");

It prints:

visit 0 (distance 0)
      -> 1 first reached, distance 1
      -> 2 first reached, distance 1
visit 1 (distance 1)
      -> 3 first reached, distance 2
visit 2 (distance 1)
      -> 6 first reached, distance 2
visit 3 (distance 2)
      -> 4 first reached, distance 3
visit 6 (distance 2)
visit 4 (distance 3)
      -> 5 first reached, distance 4
visit 5 (distance 4)

distances: [0, 1, 1, 2, 3, 4, 2]
path 0 -> 5: 0 -> 1 -> 3 -> 4 -> 5  (length 4)

The critical line is if (dist[v] != -1) continue; combined with setting dist[v] at the moment of enqueueing, not dequeuing. Mark on dequeue and a node can be pushed by several neighbours before it is processed, appear in the queue multiple times, and inflate the queue to O(edges).

parent costs one array and gives the actual route, not just its length. Walk back from the goal and reverse. Most problems that ask for a distance eventually ask for the path.

Cost: O(V + E) time and space.

Reach for it when edges are unweighted, or all the same weight. If they differ, this gives wrong answers and you want part 8.

Pattern 33 — DFS without the call stack

Recursive DFS is shorter and reads better. It also runs on a thread whose stack is, by default, 1MB — and a path of 100,000 nodes will exhaust that.

This matters more in C# than in some other languages, because a StackOverflowException cannot be caught. The runtime terminates the process. There is no exception handler, no error message you can act on, just a dead process and a verdict.

Two fixes. Convert to an explicit stack, or give the recursion a bigger stack of its own.

using System.Threading;

int n = 7;
(int, int)[] edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (4, 5), (2, 6)];
List<int>[] adj = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
foreach (var (u, v) in edges) { adj[u].Add(v); adj[v].Add(u); }

// Explicit stack. Same traversal, no call frames.
bool[] seen = new bool[n];
Stack<int> st = [];
List<int> order = [];

st.Push(0);
while (st.Count > 0)
{
    int u = st.Pop();
    if (seen[u]) continue;        // a node can be pushed several times before it is popped
    seen[u] = true;
    order.Add(u);

    // Pushed in reverse so the smallest neighbour is popped first.
    for (int i = adj[u].Count - 1; i >= 0; i--)
        if (!seen[adj[u][i]]) st.Push(adj[u][i]);
}
Console.WriteLine($"iterative DFS order: {string.Join(" -> ", order)}");

// How deep can recursion go? On the default 1MB main-thread stack, not very.
// A StackOverflowException cannot be caught in .NET — the process just dies —
// so the fix is to give the recursion its own thread with a bigger stack.
int depth = 0;
void Deep(int k) { if (k == 0) return; depth++; Deep(k - 1); }

var t = new Thread(() => Deep(500_000), 256 * 1024 * 1024);
t.Start();
t.Join();
Console.WriteLine($"recursion on a 256MB stack: reached depth {depth:N0}, no crash");

It prints:

iterative DFS order: 0 -> 1 -> 3 -> 2 -> 6 -> 4 -> 5
recursion on a 256MB stack: reached depth 500,000, no crash

The explicit version has one subtlety: if (seen[u]) continue; after the pop. A node can be pushed by several neighbours before it is ever popped, so the same index legitimately appears on the stack more than once and must be skipped on the later visits. Pushing neighbours in reverse order makes the traversal match what the recursive version would have done.

The thread trick is the other route, and it is what a lot of contest C# does. new Thread(action, 256 * 1024 * 1024) gives the recursion a quarter-gigabyte of stack, and the output above shows half a million frames with no trouble at all. It keeps the recursive code, which for tree DP is a genuine advantage.

Reach for it when the graph is deep — a path graph, a degenerate tree, a grid traversed the long way. If depth could exceed a few tens of thousands, do not leave it recursive on the main thread.

Pattern 34 — Flood fill

Connected components on a grid. Count the islands.

string[] grid =
[
    "11000",
    "11000",
    "00100",
    "00011",
];

int rows = grid.Length, cols = grid[0].Length;
bool[,] seen = new bool[rows, cols];
int islands = 0;

int[] dr = [-1, 1, 0, 0];
int[] dc = [0, 0, -1, 1];

for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
{
    if (grid[r][c] != '1' || seen[r, c]) continue;

    islands++;
    List<(int, int)> cells = [];
    Queue<(int r, int c)> q = [];
    q.Enqueue((r, c));
    seen[r, c] = true;

    while (q.Count > 0)
    {
        var (cr, cc) = q.Dequeue();
        cells.Add((cr, cc));
        for (int d = 0; d < 4; d++)
        {
            int nr = cr + dr[d], nc = cc + dc[d];
            // One bounds check, and mark on ENQUEUE not on dequeue.
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] != '1' || seen[nr, nc]) continue;
            seen[nr, nc] = true;
            q.Enqueue((nr, nc));
        }
    }
    Console.WriteLine($"island {islands}: {cells.Count} cells  {string.Join(" ", cells.Select(x => $"({x.Item1},{x.Item2})"))}");
}

Console.WriteLine($"\nislands: {islands}");

It prints:

island 1: 4 cells  (0,0) (1,0) (0,1) (1,1)
island 2: 1 cells  (2,2)
island 3: 2 cells  (3,3) (3,4)

islands: 3

The grid is a graph; the only difference is that neighbours are computed instead of stored. The dr/dc arrays keep that to one loop rather than four copied blocks, and adding diagonals means adding four entries rather than four more blocks.

Two habits are worth keeping. Bounds are checked before the grid is read, in the same guard, because C# evaluates || left to right and the order is what stops the index being out of range. And seen is set on enqueue, for exactly the reason it was in pattern 32.

BFS is used here rather than DFS specifically because a large blob of cells is exactly the deep-recursion case from pattern 33. A 500×500 grid of all ones is a single component 250,000 cells deep.

Cost: O(rows × cols).

Reach for it when the problem is a grid — islands, regions, paint filling, spreading over time.

Pattern 35 — Topological sort, and the free cycle check

Order the nodes so every edge points forwards. Task scheduling, build dependencies, course prerequisites.

Kahn’s algorithm: count how many edges point at each node, start with the ones nobody points at, and each time you remove a node, decrement its targets.

int n = 6;
// A directed graph: an edge u -> v means u must come before v.
(int u, int v)[] edges = [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)];

static List<int>? TopoSort(int n, (int u, int v)[] edges)
{
    List<int>[] outs = [.. Enumerable.Range(0, n).Select(_ => new List<int>())];
    int[] indeg = new int[n];
    foreach (var (u, v) in edges) { outs[u].Add(v); indeg[v]++; }

    // Everything with nothing pointing at it can go first.
    Queue<int> ready = new(Enumerable.Range(0, n).Where(i => indeg[i] == 0));
    List<int> order = [];

    while (ready.Count > 0)
    {
        int u = ready.Dequeue();
        order.Add(u);
        foreach (int v in outs[u])
            if (--indeg[v] == 0) ready.Enqueue(v);
    }

    // Anything left has a cycle behind it: its in-degree never reached zero.
    return order.Count == n ? order : null;
}

Console.WriteLine($"in-degrees start: {string.Join(", ", Enumerable.Range(0, n).Select(i => $"{i}:{edges.Count(e => e.v == i)}"))}");
var order = TopoSort(n, edges);
Console.WriteLine($"order: {(order is null ? "IMPOSSIBLE" : string.Join(" -> ", order))}");

// Every edge must point forwards in the result.
int[] pos = new int[n];
for (int i = 0; i < order!.Count; i++) pos[order[i]] = i;
Console.WriteLine($"every edge points forwards: {edges.All(e => pos[e.u] < pos[e.v])}");

Console.WriteLine();
(int u, int v)[] cyclic = [(0, 1), (1, 2), (2, 0)];
Console.WriteLine($"with a cycle 0->1->2->0: {(TopoSort(3, cyclic) is null ? "IMPOSSIBLE — detected" : "sorted?!")}");

It prints:

in-degrees start: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0
order: 4 -> 5 -> 2 -> 0 -> 3 -> 1
every edge points forwards: True

with a cycle 0->1->2->0: IMPOSSIBLE — detected

The cycle detection is the part worth noticing, because it is not a separate pass. If the queue empties before all n nodes are emitted, whatever is left still has something pointing at it — and since nothing outside the cycle can be pointing at all of them, there must be a cycle. order.Count == n is the whole check.

The verification line is a good habit for any ordering problem: build a position lookup and assert every edge points forwards. Topological orders are usually not unique, so comparing against one expected answer is the wrong test.

Cost: O(V + E).

Reach for it when the problem describes dependencies, prerequisites, or ordering constraints — and whenever you need to know whether a directed graph has a cycle at all.

What to remember

• List<List<int>> allocates an object per node. Fine for small graphs; at 10⁵ nodes, CSR is two arrays for the whole thing and the neighbours are contiguous.

• head is built with a prefix sum over degrees, and has n+1 cells so the last node’s end offset exists.

• BFS is shortest-path only because of the layering. No distance comparisons, and that is exactly what stops working when edges have weights.

• Mark nodes when you enqueue them, never when you dequeue them. Otherwise the same node enters the queue several times.

• A StackOverflowException cannot be caught in .NET. Deep recursion does not throw; it kills the process. Use an explicit stack, or a thread with a big stack.

• A node can legitimately be on the explicit stack twice. Check seen after popping, not only before pushing.

• order.Count == n is the cycle check. Nothing more is needed, and nothing less will do.

Part 8 adds weights, where BFS stops being correct: Dijkstra with PriorityQueue, the 0-1 case where the heap is pure overhead, and union-find.