C# 中的 Dijkstra、0-1 BFS 与并查集

边一旦带权，BFS 就不再正确。Dijkstra 能解决；C# 的 PriorityQueue 没有 DecreaseKey，只能重复入队。如果每条边的权重都是 0 或 1，堆其实纯属多余。

第 7 篇的 BFS 之所以正确，是因为每条边的代价都一样。给边加上权重，它就不再正确了：跳数更多的路径现在可能更便宜，而 BFS 认定了最先到达的那条。

下面每个程序都是完整的，都在 .NET 10 上运行过，输出直接从运行结果粘贴而来。

模式 36 — Dijkstra

每次总是扩展尚未确定的节点中代价最小的那个，而不是跳数最少的那个。节点一旦这样被扩展，它的距离就定了，因为通往它的其他路线都必须经过某个已经更贵的节点。

PriorityQueue<TElement, TPriority> 负责干活。它缺的是 DecreaseKey：没有办法伸进堆里调低某个节点的优先级。所以 C# 用惰性做法：距离变小时，把节点再压入一次，等过期的那份最终浮出来时再丢掉。

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]}.");

输出：

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.

推演的最后一行，就是这个模式在起作用。节点 1 先以距离 10 压入，之后距离变成 2，又压入一次。两个条目都在堆里；好的那个先出来，确定了节点 1 的距离；过期的那个最后浮出来，被 if (d > dist[u]) continue; 跳过。

惰性删除就只有这一行。漏掉它，节点会以错误的距离被扩展两次。

输出也说明了为什么这里 BFS 不够用。0 -> 1 只跳一次，代价 10；0 -> 2 -> 1 跳两次，代价 2。BFS 会选第一条，而且不会回头重新考虑。

代价：O(E log V)，堆里最多有 O(E) 个条目，而不是 O(V)。这是没有 DecreaseKey 的代价，几乎总是值得。

适用场景：边权非负。负权会彻底推翻“确定了就不再变”的论证，那时你需要 Bellman–Ford。

模式 37 — 0-1 BFS

再看一个经常出现的特例：每条边的代价要么是 0，要么是 1。拆墙代价 1，走路代价 0；换乘代价 1，不换乘代价 0。

Dijkstra 能用，但做了多余的功。堆的作用是在前沿里找出最小的距离，而只有 0 边和 1 边时，前沿里永远只有两种不同的距离：d 和 d+1。

所以用双端队列存前沿。0 边得到的距离不变，放到队首。1 边得到的距离多 1，放到队尾。双端队列始终有序，完全不需要比较。

// 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)}]");

输出：

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 没了。在大网格上，这是实实在在的差距，而且代码比它取代的 Dijkstra 还短。

这也是第 5 篇费劲写环形缓冲区的原因。上面为了清楚起见用了 LinkedList<int>，每次压入都要分配一个节点。

代价：O(V + E)。

适用场景：每条边的权重都是 0 或 1。认出这一点就是全部的功夫：题目会用文字来描述，而不是直接给数字。

模式 38 — 并查集

换一个问题：不问两个节点相距多远，只问它们到底连不连通，而且连接是一条一条陆续加进来的。

每个集合是一棵树，每个节点指向自己的父节点。两个节点能走到同一个根，就在同一个集合里。有两个优化能让这几乎不花代价，两个都要用上。

按秩合并（这里按集合大小）把小树挂到大树下面，树的深度增长得很慢。路径压缩把沿途经过的每个节点都直接指向根，所以每问一次，下一次就更便宜。

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()}");

输出：

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

重点是中间那两行 parent。合并完之后，节点 3 指向 2，2 再指向 0，要跳两次。对每个节点调用一次 Find 之后，所有节点都直接指向自己的根。

这里的 Find 用的是路径减半：每一步执行 parent[x] = parent[parent[x]]。它是迭代写法，不会像递归版本那样在退化的树上把栈撑爆，压平的效果也差不多。

Union 返回 bool 值得保留。false 表示两个节点本来就连通，而这正是下一个模式需要的环检测。

代价：每次操作均摊 O(α(n))。α 是反阿克曼函数，对任何能装进内存的 n 都小于 5。实际上就是常数。

适用场景：连接是陆续加进来的，而你需要判断连通性、统计连通分量或者检测环。并查集没法把集合重新拆开；如果需要拆开，那就是另一类问题了。

模式 39 — Kruskal 最小生成树

用尽可能小的代价把所有节点连起来。

把边按权重排序，依次取每条边，除非它的两个端点已经连通。就这么简单：贪心选择是正确的，而并查集让连通性检查变得很快。

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}");

输出：

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 返回 false，本身就是环检测。不需要另外遍历，也不需要 visited 数组。输出里跳过的三条边，每一条都会形成一个环。

最后的计数是一次免费的正确性检查：n 个节点的生成树恰好有 n-1 条边。少了就说明图不连通，这种情况通常应该报告出来，而不是忽略。

代价：排序 O(E log E)，并查集部分实际上是 O(E)。

适用场景：需要最小生成树，或者要以最小代价连接所有点。另一种选择是 Prim 算法，在稠密图上更好；Kruskal 更不容易写错。

模式 40 — 有向图中的环

第 7 篇用计数检测有向图的环：拓扑排序输出的节点少于 n 个，就有环。这能告诉你环存在，却不能告诉你环在哪里。

三色标记可以。白色表示没碰过，灰色表示在你当前所走的路径上，黑色表示已经处理完。

遇到灰色节点，说明有一条边指回了你脚下的路径，这就是环。遇到黑色节点，只是一个已经探索完的节点，完全正常，不是环。把这两种情况合并成一个“已访问”标记，是经典的 bug：它会在无环图里报出环来。

// 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!)}");

输出：

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

第一个图里，节点 3 从 1 和 2 都能到达。只用一个 visited 标记，会看到 3 被访问两次，就判定有环。三色标记能看出 3 是黑色的，已经处理完，不在当前路径上，于是正确地报告没有环。

因为 parent 是往下走时记录的，所以从灰色节点往回走，就能还原出具体的环。

无向图完全不需要这些：用模式 38 的并查集，两个端点已经连通的边就构成环。

代价：O(V + E)。

适用场景：你需要环本身，而不只是知道它存在，比如死锁报告、必须指出循环在哪里的依赖错误。

要点

• 权重会让 BFS 失效。跳数多的路径可能更便宜。只要边的代价不全相同，BFS 就是错的，而不只是慢。
• C# 的 PriorityQueue 没有 DecreaseKey。把变小的距离作为第二个条目压入，再用 if (d > dist[u]) continue; 跳过过期条目。
• 边权全是 0 或 1，就完全不需要堆。0 边放队首，1 边放队尾，双端队列自然有序。
• 并查集两个优化都要用。按秩合并让树保持浅，路径压缩压平剩下的深度。只用其中一个，效果明显更差。
• 路径减半是迭代写法。没有递归，所以在退化的树上也不会栈溢出。
• Union 返回 false 就是环检测。Kruskal 不需要别的，无向图的环检测也一样。
• 用三种颜色，而不是一个已访问标记。灰色表示在当前路径上，黑色表示已处理完。把它们合并，会报出不存在的环。

第 9 篇讲动态规划：五种形态，以及一个会悄悄把其中一种变成另一个问题的循环方向。