企业官网建设流程全解析

Kruskal凭什么每次选便宜边？从一个环讲清贪心为什么成立

Kruskal的步骤很短：按边权从小到大考虑，连接不同连通块就选，成环就跳过。

但读到这里，很容易继续问：每次选便宜的，最后怎么就能保证总权重最小？不成环似乎只是保证没有多余回路，和最便宜之间还差了一步。

我们从一个具体疑问讲起：如果A、B已经有一条绕行路径，又加一条便宜的AB，形成环后该删哪条？不先堆定理名字，先把这件事看明白。

1. 先确定我们要最小化什么

给一个连通、无向、带权图，要选一些边，让全部顶点连通且不形成环，并使选中全部边的总权重最小。这就是最小生成树，n个顶点需要n-1条边。

它不要求任意两点之间的路径都最短。例如：

AC=2，CB=3，AB=4

选AC、CB，总权重5，比另外两种树的6、7都小；但是A到B的路径权重5，比直连AB的4大。这并不矛盾：所有点都要连起来，单独选AB还没解决C。

如果输入图不连通，就没有覆盖全部顶点的生成树。程序要明确报告不连通，不能把某个局部连通结果叫作整个图的最小生成树。

2. 先把“权边+跳过”走一遍

采用这四条边，字母是顶点名：

AC=1，CD=2，DB=2，AB=2

相同权重可以任选处理顺序。例如AC、AB、CD、DB：

实际程序选到n-1条就可以结束，不必再检查最后一条。选出的树总权重1+2+2=5。

“已经连通”不是“这个顶点出现过”。第二步A已经出现，AB仍然要选，因为它接进了另一块里的B。

3. 为什么排除环还不够？

如果先选贵边，也完全可能不成环：

AB=1，BC=2，AC=9 先选AC和BC：不成环，三个点连通，总权重11 选AB和BC：同样合法，总权重3

因此要把两件事分开：

• 不成环，让选中的结构合法。
• 按权重处理，再解释选择不会吃亏，才有最优性的依据。

“贪心”这个名字不能代替理由。很多问题中，眼前最便宜的选择确实会让后面吃亏；这里必须解释为什么不会。

4. 你的例子：加AB之后，究竟删哪条？

假设有一套原方案：

A ─1─ C ─2─ D ─2─ B 总权重：5

现在加上AB=2，形成一个环：

A ─1─ C ─2─ D ─2─ B └────────2────────┘ 暂时总权重：7

环提供了两条绕行方向，所以删掉其中任何一条边，仍可连接所有点。但成本不一样：

这里的“原来A到B是5”指三条边的和，不是一条可直接删掉的边。删掉整条绕行路径，会把中间顶点丢在外面。

真正有效的是：加一条2，换掉环里一条至少为2的边。原方案如果已经最优，交换后不涨价，就仍然最优，同时接受了我们想选的AB。

注意，这一步是在比较方案，不是Kruskal实际运行时先把环造出来再删边。实际算法始终维护无环结构。

5. 不只是这个例子：每一步为什么都换得到？

想象算法已经连好几片区域。每片区域内部是此前选中的边，区域之间还没有连起来。

现在准备选一条边，连接两个不同区域。它是当前最便宜的可选边。我们问：有没有一套最优方案，偏偏没有它？

如果最优方案本来就有它，当然可以放心选。如果没有，就做一次我们刚才看到的交换。

第一步：在一套包含此前所有已选边的最优方案里，加上这条新边。

因为原方案连通，两端本来有一条路径，加边就形成一个环。

第二步：沿原来的路径，找一条走出当前区域的边。

新边的一端在区域里，另一端在外面。原来的绕行路径也必须从内部走到外部，总得跨一次区域边界。

这条跨出去的旧边，不是我们此前选好的边：此前选好的边全部位于当前区域内部。删掉它，就不会撤销前面的选择。

第三步：这条旧边不会比新边更便宜。

为什么？如果更便宜，按从小到大的顺序，算法早就考虑过它了。它的两端现在属于不同区域，以前也不可能已经连通，因为连通块只会合并，不会分裂。所以当时它一定会被选，而不会因成环跳过。那两个区域现在早就合在一起了，与眼前的情况矛盾。

所以这条旧边的权重，至少等于我们正在选的新边。加新边、删旧边，全部点仍连通，也没有环，总成本不增加。

结果：最优方案能接纳新边，而且此前的选择全部保留。

这段解释最重要的不是“形成环”三个字，而是同时保证两件事：换边不涨价；换掉的不是前面已经选好的边。

6. 为什么局部安全，能走到整体最优？

刚开始一条边都没选，任何最优方案都兼容。每次选择之后，我们都能把一套最优方案改成继续包含全部已选边的方案。

所以算法不是“希望最后还能拼成最优”，而是每走一步，都还有一套最优方案保留着这些选择。

等我们选满n-1条并连通所有点，最优方案也只有n-1条边，不可能再塞别的边。它就是算法已经选出的这些边。因此得到的总权重最小。

相同权重时，换掉同权边，成本不变，可能有多棵不同的最小生成树。测试不能要求所有实现输出同一组边。

7. C实现里，“是否成环”怎么判断？

不用每次真的画出路径。用并查集记录连通块：

find(u) == find(v)：两端已连通，跳过 find(u) != find(v)：连接两块，选边并合并

并查集的代表编号不是顶点是否访问过，也不是最短路距离。它只回答哪些顶点已经通过所选边连在一起。

附录程序先复制边表再排序，不改调用者输入；比较器用大小关系判断，不用weight相减，避免极端整数相减溢出。总权重使用int64_t。相同权重用原始边编号决定处理顺序，只为了输出可复现，不意味着该边集唯一。

核心流程可以先这样读，完整可编译实现见附录：

按权重给边排序 每个顶点先独立成一块 依次考虑(u,v,weight)： 如果u、v同块：跳过 否则：记录边，累加权重，合并两块 记录到n-1条后结束 不足n-1条：报告原图不连通

通常用排序加并查集描述成本：排序O(m log m)，初始化O(n)，路径压缩与按大小合并的并查集操作合计摊还O(m α(n))。α(n)增长极慢，但不是数学上永远为常数。这里n为顶点数，m为边数；复杂度表也不能代替前面的最优性解释。

这个界按使用O(m log m)排序实现分析，不是C标准对qsort最坏耗时的承诺。复制边表、保存并查集与结果需要O(m+n)额外空间。

本文固定容量的小图程序用于学习和验证，n不超过6、m不超过15，约定顶点0..n-1、边id与输入下标一致。一般算法可换成动态容量；别把固定教学上限误当算法只能处理6个点。

8. 不拿两个贪心算法互相证明

验证时不能只写Kruskal和Prim，发现两者一样就放心：两个实现可能共享错误。

这里给小图写一个独立、慢但直接的参考：枚举所有恰有n-1条边的子集，用广度遍历检查是否连通，再计算权重，取最小值。

对于本文无向简单图，n-1条边且覆盖全部顶点连通，就是一棵树。不需要把待测算法的并查集复制进参考检查器。枚举成本指数级，只用于小规模验证，不用于实际求解。

每次测试检查：算法是否正确报告连通性；已选边来自输入且无重复；权重和正确；连通结果有n-1条边且覆盖全部点；总权重等于穷举最小值。不连通图只核对“不存在整个图的生成树”及返回边身份，不宣称穷举验证了最小生成森林的权重。

覆盖四顶点六条候选边，每条可不存在或取-1、0、2，穷举4^6=4096个图；再加固定种子1000个随机小图、用户例子、整数极值、环后桥边和6种等权处理顺序。负权和零权没有特殊禁令，换边理由仍适用。

两个错误候选也要能区分：直接取三角形的三条便宜边，可能已凑满n-1却漏掉另一顶点；先取贵边得到合法树，仍可能比最优贵。前者检验结构，后者检验权重。它们是明确构造的错误候选，不冒称跑了完整变异算法。

本轮实际环境为Windows x64、MinGW GCC 13.1.0、C11、-Wall -Wextra -Werror -O2，断言开启。5107个图用例通过，其中4755个连通、352个不连通；没有sanitizer检查或性能计时。完整源码运行输出：

user_example: connected=1 edges=3 total=5 exchange add AB=2 remove id=0: total=6 exchange add AB=2 remove id=1: total=5 exchange add AB=2 remove id=2: total=5 integer_extremes: connected=1 edges=2 total=-2147483648 sum_beyond_int_positive: connected=1 edges=2 total=4294967294 sum_beyond_int_negative: connected=1 edges=2 total=-4294967296 cycle_then_bridge: connected=1 edges=3 total=13 bad candidate without cycle check: rejected; first 3 edges leave D disconnected bad candidate expensive-first: rejected; valid tree 11 > optimum 3 PASS cases=5107 connected=4755 disconnected=352; equal orders=6; exchange removals=3

交换输出的id=0、1、2分别是AC、CD、DB：删AC涨到6，删CD或DB仍是5。六种等权顺序的树可能不同，但全部达到总权重5。integer_extremes的最优值超出一般正权例子的直觉，验证总和与排序比较没有依赖非负权。

程序枚举的是小规模候选树，给实验提供独立答案；有限测试不能代替第5、6节的通用换边理由。

9. 这次真正理解的是哪一步？

“先选便宜的，成环就跳过”是操作方法；“最优方案可以接纳这条边，换掉不更便宜的边，又不撤销以前的选择”才是理由。

所以回到最开始那个疑问，答案不是“贪心当然正确”，也不是“路径总和比直连更低”，而是：选择能够被一套最优方案完整保留，直到最后。

附录：完整程序

把下面源码作为verify.c编译。assert用于检查与前置条件，本验证不得添加-DNDEBUG。随机种子固定为20261005。当前测试针对无向简单图，单顶点空边图也会出现；不覆盖平行边和自环。容量与整数类型在上面已说明。

gcc -std=c11 -Wall -Wextra -Werror -O2 verify.c -o verify ./verify

#include <assert.h> #include <limits.h> #include <stdint.h> #include <stdio.h> #include <stdlib.h> #include <string.h> enum { MAX_N = 6, MAX_M = 15 }; typedef struct { int u, v, weight, id; } Edge; typedef struct { int connected, count, ids[MAX_N]; int64_t total; } Result; static int find_root(int parent[], int x) { if (parent[x] != x) parent[x] = find_root(parent, parent[x]); return parent[x]; } static int compare_edge(const void *p, const void *q) { const Edge *a = p, *b = q; if (a->weight != b->weight) return (a->weight > b->weight) - (a->weight < b->weight); return (a->id > b->id) - (a->id < b->id); } static Result kruskal(int n, const Edge input[], int m) { assert(n >= 1 && n <= MAX_N && m >= 0 && m <= MAX_M); Edge edges[MAX_M]; int parent[MAX_N], size[MAX_N]; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } for (int i = 0; i < m; i++) { assert(input[i].u >= 0 && input[i].u < n && input[i].v >= 0 && input[i].v < n); assert(input[i].id == i); edges[i] = input[i]; } qsort(edges, (size_t)m, sizeof(Edge), compare_edge); Result result = {0}; for (int i = 0; i < m && result.count < n - 1; i++) { int a = find_root(parent, edges[i].u); int b = find_root(parent, edges[i].v); if (a == b) continue; if (size[a] < size[b]) { int temp = a; a = b; b = temp; } parent[b] = a; size[a] += size[b]; result.ids[result.count++] = edges[i].id; result.total += edges[i].weight; } result.connected = result.count == n - 1; return result; } // Oracle uses graph traversal, not the algorithm's union-find. static int connected_subset(int n, const Edge edges[], int m, unsigned mask) { int seen[MAX_N] = {1}, queue[MAX_N] = {0}; int head = 0, tail = 1; while (head < tail) { int x = queue[head++]; for (int i = 0; i < m; i++) if (mask & (1u << i)) { int y = edges[i].u == x ? edges[i].v : edges[i].v == x ? edges[i].u : -1; if (y >= 0 && !seen[y]) { seen[y] = 1; queue[tail++] = y; } } } return tail == n; } static int bit_count(unsigned mask) { int count = 0; while (mask) { mask &= mask - 1; count++; } return count; } static int64_t brute_force(int n, const Edge edges[], int m) { int64_t best = INT64_MAX; for (unsigned mask = 0; mask < (1u << m); mask++) { if (bit_count(mask) != n - 1 || !connected_subset(n, edges, m, mask)) continue; int64_t total = 0; for (int i = 0; i < m; i++) if (mask & (1u << i)) total += edges[i].weight; if (total < best) best = total; } return best; } static unsigned cases, connected_cases, disconnected_cases; static void check(int n, const Edge edges[], int m, const char *label) { Result r = kruskal(n, edges, m); int64_t best = brute_force(n, edges, m); assert(r.connected == (best != INT64_MAX)); unsigned mask = 0; int64_t total = 0; for (int i = 0; i < r.count; i++) { int id = r.ids[i]; assert(id >= 0 && id < m && !(mask & (1u << id))); mask |= 1u << id; total += edges[id].weight; } assert(total == r.total); if (r.connected) { assert(r.count == n - 1 && connected_subset(n, edges, m, mask)); assert(r.total == best); connected_cases++; } else disconnected_cases++; if (label) printf("%s: connected=%d edges=%d total=%lld\n", label, r.connected, r.count, (long long)r.total); cases++; } static uint32_t state = 20261005u; static uint32_t next_random(void) { state ^= state << 13; state ^= state >> 17; state ^= state << 5; return state; } int main(void) { Edge edges[MAX_M]; const int weights[] = {-1, 0, 2}; // Each of the six possible edges is absent, -1, 0, or 2: 4^6 graphs. for (int code = 0; code < 4096; code++) { int rest = code, m = 0; for (int u = 0; u < 4; u++) for (int v = u + 1; v < 4; v++) { int option = rest % 4; rest /= 4; if (option) { edges[m] = (Edge){u, v, weights[option - 1], m}; m++; } } check(4, edges, m, NULL); } for (int trial = 0; trial < 1000; trial++) { int n = 1 + (int)(next_random() % MAX_N), m = 0; for (int u = 0; u < n; u++) for (int v = u + 1; v < n; v++) { if (next_random() % 4 != 0) { edges[m] = (Edge){u, v, (int)(next_random() % 21) - 10, m}; m++; } } check(n, edges, m, NULL); } const Edge user[] = {{0,2,1,0}, {2,3,2,1}, {3,1,2,2}, {0,1,2,3}}; check(4, user, 4, "user_example"); unsigned original = (1u << 0) | (1u << 1) | (1u << 2); assert(connected_subset(4, user, 4, original)); for (int remove = 0; remove < 3; remove++) { unsigned replaced = (original | (1u << 3)) & ~(1u << remove); assert(connected_subset(4, user, 4, replaced)); printf("exchange add AB=2 remove id=%d: total=%d\n", remove, 7-user[remove].weight); } // Reorder equal-weight edges in all six ways; no single tree is required. for (int a = 1; a <= 3; a++) for (int b = 1; b <= 3; b++) for (int c = 1; c <= 3; c++) { if (a == b || b == c || a == c) continue; Edge reordered[] = {user[0], user[a], user[b], user[c]}; for (int i = 0; i < 4; i++) reordered[i].id = i; check(4, reordered, 4, NULL); } const Edge wide[] = {{0,1,INT_MIN,0}, {1,2,INT_MAX,1}, {0,2,0,2}}; check(3, wide, 3, "integer_extremes"); const Edge large_positive[] = {{0,1,INT_MAX,0}, {1,2,INT_MAX,1}}; const Edge large_negative[] = {{0,1,INT_MIN,0}, {1,2,INT_MIN,1}}; check(3, large_positive, 2, "sum_beyond_int_positive"); check(3, large_negative, 2, "sum_beyond_int_negative"); const Edge cycle[] = {{0,1,1,0},{1,2,2,1},{0,2,3,2},{2,3,10,3}}; check(4, cycle, 4, "cycle_then_bridge"); assert(!connected_subset(4, cycle, 4, 7u)); puts("bad candidate without cycle check: rejected; first 3 edges leave D disconnected"); const Edge expensive[] = {{0,1,1,0},{1,2,2,1},{0,2,9,2}}; assert(connected_subset(3, expensive, 3, 6u)); assert(expensive[1].weight + expensive[2].weight > brute_force(3, expensive, 3)); puts("bad candidate expensive-first: rejected; valid tree 11 > optimum 3"); printf("PASS cases=%u connected=%u disconnected=%u; equal orders=6; exchange removals=3\n", cases, connected_cases, disconnected_cases); return 0; }