Dijkstra, 0-1 BFS and Union-Find in C#

Part 7’s BFS was correct because every edge cost the same. Give edges weights and it stops being correct — a path with more hops can now be cheaper, and BFS commits to the first arrival.

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

Pattern 36 — Dijkstra

Always expand the cheapest unsettled node rather than the nearest in hops. Once a node is expanded that way its distance is final, because every other route to it would have to go through something already more expensive.

PriorityQueue<TElement, TPriority> does the work. What it does not have is DecreaseKey — there is no way to reach into the heap and lower a node’s priority. So C# uses the lazy approach: when a distance improves, push the node again, and discard the outdated copy when it eventually surfaces.

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

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

int[] dist = new int[n];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;

// C# has no DecreaseKey, so stale entries are pushed and skipped on the way out.
PriorityQueue<int, int> pq = new();
pq.Enqueue(0, 0);

while (pq.TryDequeue(out int u, out int d))
{
    if (d > dist[u]) { Console.WriteLine($"  skip stale entry for {u} (d={d}, best is {dist[u]})"); continue; }
    Console.WriteLine($"settle {u} at distance {d}");

    foreach (var (v, w) in adj[u])
    {
        if (dist[u] + w >= dist[v]) continue;
        dist[v] = dist[u] + w;
        pq.Enqueue(v, dist[v]);
        Console.WriteLine($"      -> {v} improved to {dist[v]}");
    }
}

Console.WriteLine($"\ndistances from 0: [{string.Join(", ", dist)}]");
Console.WriteLine($"\nBFS would call 0->1 one hop and stop there, costing 10.");
Console.WriteLine($"Dijkstra takes 0->2->1, two hops, costing {dist[1]}.");

It prints:

settle 0 at distance 0
      -> 1 improved to 10
      -> 2 improved to 1
settle 2 at distance 1
      -> 1 improved to 2
      -> 4 improved to 9
settle 1 at distance 2
      -> 3 improved to 4
settle 3 at distance 4
      -> 5 improved to 8
settle 5 at distance 8
settle 4 at distance 9
  skip stale entry for 1 (d=10, best is 2)

distances from 0: [0, 2, 1, 4, 9, 8]

BFS would call 0->1 one hop and stop there, costing 10.
Dijkstra takes 0->2->1, two hops, costing 2.

The last line of the trace is the pattern working. Node 1 was pushed at distance 10, then improved to 2 and pushed again. Both entries sat in the heap; the good one came out first and settled the node; the stale one surfaced at the end and was skipped by if (d > dist[u]) continue;.

That one line is the whole of lazy deletion. Leave it out and nodes get expanded twice with wrong distances.

The output also shows why BFS is not enough here. 0 -> 1 is a single hop costing 10; 0 -> 2 -> 1 is two hops costing 2. BFS would take the first and never reconsider.

Cost: O(E log V), with a heap holding up to O(E) entries rather than O(V) — the price of no DecreaseKey, and almost always worth paying.

Reach for it when edges have non-negative weights. Negative weights break the “settled is final” argument entirely, and you need Bellman–Ford.

Pattern 37 — 0-1 BFS

Now a special case that comes up constantly: every edge costs either 0 or 1. Breaking a wall costs 1 and walking costs 0; changing lines costs 1 and staying on one costs 0.

Dijkstra works. It is also doing needless work. The heap exists to find the smallest distance on the frontier, and with only 0- and 1-edges the frontier only ever holds two distinct distances — d and d+1.

So keep the frontier in a deque. A 0-edge produces the same distance, so it goes at the front. A 1-edge produces one more, so it goes at the back. The deque stays sorted with no comparisons at all.

// Every edge costs 0 or 1. A heap still works, and is pure overhead: with only
// two possible distances in play, a deque keeps the frontier sorted for free.
int n = 6;
(int u, int v, int w)[] edges =
[
    (0, 1, 0), (1, 2, 1), (0, 2, 1), (2, 3, 0), (3, 4, 1), (1, 4, 1), (4, 5, 0),
];

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

int[] dist = new int[n];
Array.Fill(dist, int.MaxValue);
dist[0] = 0;

LinkedList<int> dq = [];
dq.AddFirst(0);

while (dq.Count > 0)
{
    int u = dq.First!.Value;
    dq.RemoveFirst();
    Console.WriteLine($"take {u} (distance {dist[u]})");

    foreach (var (v, w) in adj[u])
    {
        if (dist[u] + w >= dist[v]) continue;
        dist[v] = dist[u] + w;

        // Weight 0 keeps the same distance, so it belongs at the FRONT.
        // Weight 1 is one further out, so it belongs at the BACK.
        if (w == 0) { dq.AddFirst(v); Console.WriteLine($"      -> {v} = {dist[v]}  (0-edge, push FRONT)"); }
        else        { dq.AddLast(v);  Console.WriteLine($"      -> {v} = {dist[v]}  (1-edge, push BACK)"); }
    }
}

Console.WriteLine($"\ndistances: [{string.Join(", ", dist)}]");

It prints:

take 0 (distance 0)
      -> 1 = 0  (0-edge, push FRONT)
      -> 2 = 1  (1-edge, push BACK)
take 1 (distance 0)
      -> 4 = 1  (1-edge, push BACK)
take 2 (distance 1)
      -> 3 = 1  (0-edge, push FRONT)
take 3 (distance 1)
take 4 (distance 1)
      -> 5 = 1  (0-edge, push FRONT)
take 5 (distance 1)

distances: [0, 0, 1, 1, 1, 1]

log V disappears. On a large grid that is a real difference, and the code is shorter than the Dijkstra it replaces.

This is also why part 5 bothered with a ring buffer. LinkedList<int> is used above for clarity and allocates a node per push.

Cost: O(V + E).

Reach for it when every edge weight is 0 or 1. Recognising that is the whole skill — the problem will describe it in words, not numbers.

Pattern 38 — Union-Find

A different question: not how far apart two nodes are, but merely whether they are connected at all — with the connections arriving one at a time.

Each set is a tree, and each node points at its parent. Two nodes are in the same set when they reach the same root. Two optimisations make this almost free, and you want both.

Union by size hangs the smaller tree under the bigger one, so depth grows slowly. Path compression re-points every node it walks past straight at the root, so asking a question makes the next question cheaper.

int n = 8;
int[] parent = [.. Enumerable.Range(0, n)];
int[] size = [.. Enumerable.Repeat(1, n)];

// Path HALVING: iterative, so it cannot overflow the stack, and it flattens
// the tree as it walks.
int Find(int x)
{
    while (parent[x] != x)
    {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

bool Union(int a, int b)
{
    int ra = Find(a), rb = Find(b);
    if (ra == rb) return false;                       // already together
    if (size[ra] < size[rb]) (ra, rb) = (rb, ra);     // hang the smaller tree off the bigger
    parent[rb] = ra;
    size[ra] += size[rb];
    return true;
}

foreach (var (a, b) in new[] { (0, 1), (2, 3), (1, 2), (4, 5), (6, 7), (5, 6) })
{
    bool merged = Union(a, b);
    Console.WriteLine($"union({a},{b}) {(merged ? "merged " : "no-op  ")}  parent = [{string.Join(",", parent)}]");
}

// Snapshot BEFORE any Find runs — a Find is what does the flattening, so
// asking a question first would hide the effect.
Console.WriteLine($"\nafter the unions : parent = [{string.Join(",", parent)}]");
Console.WriteLine($"  node 3 points at 2, which points at 0. Two hops to the root.");

for (int i = 0; i < n; i++) Find(i);
Console.WriteLine($"after Find on all: parent = [{string.Join(",", parent)}]   <- flattened");
Console.WriteLine($"  every node now points straight at its root. One hop.");

Console.WriteLine($"\nunion(0,3) -> {Union(0, 3)}   (already in the same set)");
Console.WriteLine($"connected(0,3): {Find(0) == Find(3)}");
Console.WriteLine($"connected(0,7): {Find(0) == Find(7)}");
Console.WriteLine($"components: {Enumerable.Range(0, n).Select(Find).Distinct().Count()}");

It prints:

union(0,1) merged   parent = [0,0,2,3,4,5,6,7]
union(2,3) merged   parent = [0,0,2,2,4,5,6,7]
union(1,2) merged   parent = [0,0,0,2,4,5,6,7]
union(4,5) merged   parent = [0,0,0,2,4,4,6,7]
union(6,7) merged   parent = [0,0,0,2,4,4,6,6]
union(5,6) merged   parent = [0,0,0,2,4,4,4,6]

after the unions : parent = [0,0,0,2,4,4,4,6]
  node 3 points at 2, which points at 0. Two hops to the root.
after Find on all: parent = [0,0,0,0,4,4,4,4]   <- flattened
  every node now points straight at its root. One hop.

union(0,3) -> False   (already in the same set)
connected(0,3): True
connected(0,7): False
components: 2

The two parent lines in the middle are the point. After the unions, node 3 points at 2 which points at 0 — two hops. After one Find per node, everything points straight at its root.

Find here uses path halving: parent[x] = parent[parent[x]] each step. It is iterative, so it cannot overflow the stack the way the recursive version can on a degenerate tree, and it flattens nearly as well.

Union returning a bool is worth keeping. false means the two were already connected — which is exactly the cycle test the next pattern needs.

Cost: O(α(n)) amortised per operation. That is the inverse Ackermann function, and it is below 5 for any n that fits in memory. Constant, in practice.

Reach for it when connections arrive incrementally and you need connectivity, component counts, or cycle detection. It cannot split a set back apart — if you need that, you are in a different problem.

Pattern 39 — Kruskal’s minimum spanning tree

Connect everything as cheaply as possible.

Sort the edges by weight and take each one unless its endpoints are already connected. That is it — the greedy choice is correct, and union-find is what makes the connectivity test fast.

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

int[] parent = [.. Enumerable.Range(0, n)];
int[] size = [.. Enumerable.Repeat(1, n)];

int Find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
bool Union(int a, int b)
{
    int ra = Find(a), rb = Find(b);
    if (ra == rb) return false;
    if (size[ra] < size[rb]) (ra, rb) = (rb, ra);
    parent[rb] = ra; size[ra] += size[rb];
    return true;
}

int total = 0;
List<(int, int, int)> chosen = [];

foreach (var e in edges.OrderBy(e => e.w))
{
    bool took = Union(e.u, e.v);
    Console.WriteLine($"edge {e.u}-{e.v} weight {e.w}  {(took ? "TAKE " : "skip ")}  {(took ? "" : "both ends already connected — it would close a cycle")}");
    if (!took) continue;
    chosen.Add((e.u, e.v, e.w));
    total += e.w;
}

Console.WriteLine($"\nedges chosen: {chosen.Count}  (a tree on {n} nodes always has {n - 1})");
Console.WriteLine($"total weight: {total}");

It prints:

edge 1-2 weight 1  TAKE   
edge 1-3 weight 2  TAKE   
edge 3-4 weight 2  TAKE   
edge 0-2 weight 3  TAKE   
edge 3-5 weight 3  TAKE   
edge 0-1 weight 4  skip   both ends already connected — it would close a cycle
edge 2-3 weight 4  skip   both ends already connected — it would close a cycle
edge 4-5 weight 6  skip   both ends already connected — it would close a cycle

edges chosen: 5  (a tree on 6 nodes always has 5)
total weight: 11

Union returning false is the cycle check. No separate traversal, no visited array. The three skipped edges in the output are each one that would have closed a loop.

The final count is a free sanity check: a spanning tree on n nodes has exactly n-1 edges. Fewer means the graph was disconnected, and that is usually worth reporting rather than ignoring.

Cost: O(E log E) for the sort, and effectively O(E) for the union-find.

Reach for it when you need a minimum spanning tree, or to connect all points at minimum cost. Prim’s algorithm is the alternative and is better on dense graphs; Kruskal is easier to get right.

Pattern 40 — Cycles in a directed graph

Part 7 detected directed cycles with a counter — if the topological sort emitted fewer than n nodes, there was a cycle. That tells you a cycle exists. It does not tell you where.

Three colours does. White is untouched, grey is on the path you are currently standing on, black is finished.

Meeting a grey node means an edge back into the path under your feet, which is a cycle. Meeting a black node means a node you already finished exploring — perfectly normal, and not a cycle. Collapsing those two cases into one “visited” flag is the classic bug, and it reports cycles in acyclic graphs.

// Three colours. WHITE untouched, GREY on the current path, BLACK finished.
// Meeting a GREY node means an edge back into the path you are standing on,
// which is a cycle. Meeting BLACK is just a node you already finished.
const int White = 0, Grey = 1, Black = 2;

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

    int[] colour = new int[n];
    int[] parent = new int[n];
    Array.Fill(parent, -1);
    List<int>? cycle = null;

    bool Dfs(int u)
    {
        colour[u] = Grey;
        foreach (int v in outs[u])
        {
            if (colour[v] == Grey)
            {
                cycle = [v];
                for (int at = u; at != v; at = parent[at]) cycle.Add(at);
                cycle.Add(v);
                cycle.Reverse();
                return true;
            }
            if (colour[v] == White) { parent[v] = u; if (Dfs(v)) return true; }
        }
        colour[u] = Black;
        return false;
    }

    for (int i = 0; i < n; i++)
        if (colour[i] == White && Dfs(i)) return cycle;
    return null;
}

(int, int)[] acyclic = [(0, 1), (0, 2), (1, 3), (2, 3)];
Console.WriteLine($"0->1, 0->2, 1->3, 2->3");
Console.WriteLine($"  node 3 is reached twice, but the second time it is BLACK, not GREY.");
Console.WriteLine($"  cycle: {(FindCycle(4, acyclic) is null ? "none" : "found")}");

(int, int)[] cyclic = [(0, 1), (1, 2), (2, 3), (3, 1)];
var found = FindCycle(4, cyclic);
Console.WriteLine($"\n0->1, 1->2, 2->3, 3->1");
Console.WriteLine($"  cycle: {string.Join(" -> ", found!)}");

It prints:

0->1, 0->2, 1->3, 2->3
  node 3 is reached twice, but the second time it is BLACK, not GREY.
  cycle: none

0->1, 1->2, 2->3, 3->1
  cycle: 1 -> 2 -> 3 -> 1

The first graph has node 3 reachable from both 1 and 2. A single visited flag would see 3 twice and call that a cycle. Three colours sees that 3 is black — finished, not on the current path — and correctly reports nothing.

Because parent is recorded on the way down, the actual cycle can be reconstructed by walking back from the grey node.

For an undirected graph none of this is needed: run the union-find from pattern 38, and an edge whose endpoints are already connected is a cycle.

Cost: O(V + E).

Reach for it when you need the cycle itself rather than just its existence — deadlock reports, dependency errors that have to name the loop.

What to remember

• Weights break BFS. More hops can be cheaper. If edge costs differ at all, BFS is wrong, not just slower.

• C#’s PriorityQueue has no DecreaseKey. Push the improved distance as a second entry and skip stale ones with if (d > dist[u]) continue;.

• All edges 0 or 1 means no heap at all. Push 0-edges to the front and 1-edges to the back, and the deque stays sorted for free.

• Union-find needs both optimisations. Union by size keeps trees shallow, path compression flattens what is left. Either alone is meaningfully worse.

• Path halving is iterative. No recursion, so no stack overflow on a degenerate tree.

• Union returning false is the cycle test. Kruskal needs nothing else, and neither does undirected cycle detection.

• Three colours, not one visited flag. Grey means on the current path; black means finished. Merging them reports cycles that do not exist.

Part 9 is dynamic programming — five shapes, and the loop direction that silently turns one of them into a different problem.