第 09 章

贪心算法——1926年，一位数学家如何用最便宜的电线连接整片地区？

正在加载交互实验…

第一季 · 人类如何驯服数据

历史主线：1926—1957年 · 摩拉维亚电气化、Borůvka、Jarník、Kruskal、Prim1926年，捷克斯洛伐克，摩拉维亚地区。第一次世界大战已经结束八年，欧洲正在恢复工业生产、建设道路、扩展电力网络。城镇需要电力。工厂需要电力。偏远地区也需要接入供电系统。但是，有一个现实问题：假设有几十座城镇要连接到同一个供电网络。电线不是免费的。输电线路越长，建设成本通常越高。那么，怎样安排线路，才能在保证所有城镇连通的前提下，让总建设成本尽可能低？你可能会说：“每次选择最便宜的线路，不就行了吗？”可是，真的有这么简单？如果某条便宜的线路造成了无用的环路呢？如果眼前看起来最便宜的选择，导致后面必须修建一条昂贵线路呢？对于一般的优化问题，局部最便宜，并不意味着整体最便宜。然而，1926年，一位26岁的捷克数学家发现，在一种特殊的网络问题中，局部选择竟然可以被严格证明是安全的。他的名字叫作：Otakar Borůvka。而这次研究，后来成为组合优化和贪心算法发展史上的重要里程碑。

第一幕：一位26岁的数学家，与一个电力工程问题

Otakar Borůvka

1899—1995 · 捷克数学家他的研究横跨图论、微分几何、代数和微分方程。1926年发表的最低成本连接网络算法，是最小生成树问题最早的算法成果之一。

Borůvka 出生于奥匈帝国时期的乌赫尔堡地区，也就是今天捷克境内的 Uherské Hradiště。第一次世界大战结束后，他进入布尔诺的高等学府学习数学，并受到数学家 Matyáš Lerch 的影响。当时，数学还没有我们今天熟悉的“算法设计与分析”这一完整学科体系。甚至连现代图论的一些基础术语，也没有完全普及。但工业社会已经在不断提出数学问题。铁路怎样连接？电网怎样铺设？通信线路怎样选择？这些问题都要求：在大量可能方案之中，找出成本最低的可行方案。

一个真实的历史细节

关于 Borůvka 为什么研究这道题，后来的数学史文献记载，它源于摩拉维亚地区的电气化需求。研究任务是为当地城镇设计经济的供电连接网络。Borůvka 在1926年发表了两份相关论文，其中一篇专门面向电力网络经济建设问题。^{[DML-CZ][ScienceDirect]}这与某些纯粹出于数学兴趣而研究的问题不同。Borůvka 最初面对的，就是一个真实工程问题。当然，没有足够证据证明他在某天亲自站在施工现场、拿着地图与电力工程师争论线路，所以我们不会编造这样的情节。但我们完全可以站在他的研究问题前，重建当年的数学推理。

1926年的问题：怎样连接五座城镇？

假设现在有五座城镇：A、B、C、D、E。建设部门调查了不同线路的成本。

摩拉维亚电力线路——教学模拟地图

查看 SVG 配图原件

09-003.svg · 点击查看大图

顶点代表城镇，边代表候选线路，数字代表相对建设成本。该网络为教学设计，并非1926年实际电网图纸。

我们的任务并不是找到从 A 到 E 的最短路线。那是上一章 Dijkstra 算法解决的问题。这里的目标是：选出若干条线路，让所有城镇互相连通，同时使线路总成本最低。这个问题叫作：Minimum Spanning Tree，最小生成树，简称 MST。为什么叫“树”？因为一个没有多余环路的连通网络，恰好构成一棵树。如果有

V

个顶点，那么任意生成树都恰好包含：

V-1

条边。因此，五座城镇最终只需要四条连接线路。前提是候选线路本身能够构成连通网络。

第二幕：Borůvka 想到了什么？

我们试着重建一种自然的思考方式。假设 A 城镇尚未接入任何其他城镇。它总需要有一条线路与外界连接。那么，对于 A 而言，为什么不优先考虑最便宜的一条可用连接？在我们的模拟地图中：

A—B：2
A—D：3

因此，A 最便宜的线路是 A—B。同样，对于 C：

C—B：5
C—E：2

于是 C 最便宜的线路是 C—E。如果让每座孤立城镇都选择自己最便宜的连接，会发生什么？我们可能得到若干个小网络。然后再把这些小网络继续连接起来。这正是 Borůvka 算法的核心思想。一开始，每座城镇都是一个独立的连通分量。每一轮，让每个分量选择一条通向其他分量的最便宜线路。随后，把这些分量合并成更大的网络。重复这个过程，直到只剩下一个连通分量。

为什么这很聪明？

因为算法不是一条一条地缓慢扩展。它可以在一轮之中同时合并很多连通分量。如果每个分量至少通过一条线路与另一个分量合并，那么每轮之后，分量数量至少会大致减半。因此，只需要

O(\log V)

轮，就能够完成连接。采用适当实现，Borůvka 算法可以达到：

O(E\log V)

的时间复杂度。而这一切发生在1926年。那时，计算机算法尚未形成我们今天熟悉的研究领域。Borůvka 使用的数学表达更多来自当时的矩阵和组合数学，而不是现代算法教材中的标准图论术语。^{[ScienceDirect][DML-CZ]}这正是我觉得算法史非常迷人的地方：数学家往往先发现解决问题的方法，后来的计算机科学才逐渐建立起统一的语言去描述它。

第三幕：30年后，另一位数学家决定从最便宜的线路开始

Joseph B. Kruskal

1928—2010 · 美国数学家、统计学家除最小生成树算法之外，他还在多维尺度分析、非参数统计等领域作出重要贡献。

时间来到1956年。美国。Joseph Kruskal 在 Proceedings of the American Mathematical Society 发表了一篇只有三页的论文：On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem《图的最短生成子树与旅行商问题》。论文一开始就引用了 Borůvka 1926年的研究。所以，这不是一个完全不了解前人工作的人独立创造了整个领域的故事。Kruskal 熟悉已有结果，并提出了一套极其简洁的构造方法。^{[JSTOR][耶鲁大学计算机科学系]}

他的想法甚至可以用一句话说完

按照边的权重从小到大排序，依次选择不会形成环的边。如果一条边形成环，就跳过。如果不会形成环，就加入。直到所有顶点连通。这就是 Kruskal 算法。它的简单程度可能令人惊讶。但真正厉害的不是规则简单，而是规则能够保证全局最优。

实验一：重现1956年的 Kruskal 算法

我们继续使用刚才的五座城镇。已经按成本排序的线路是：

候选线路	成本
A—B	2
C—E	2
A—D	3
B—D	4
B—C	5
B—E	6
D—E	7

1956年的网络建设实验室

Kruskal · 按成本排序 · 检查是否形成环

0 / 7

查看 SVG 配图原件

09-005.svg · 点击查看大图

已经选中的线路

0 / 4

累计建设成本

0

所有线路已经按成本排序。准备检查最便宜的线路。

请特别观察第四条候选边：B—D，成本4此时 A—B 与 A—D 已经存在。如果再加入 B—D，就会产生：A → B → D → A一个环。形成环意味着：即使去掉环中的某条边，网络仍然可能保持连通。而如果所有建设成本均为正，保留这种多余的连接通常会增加总成本。因此，Kruskal 算法拒绝这条边。最终选择：A—B (2)、C—E (2)、A—D (3)、B—C (5)总代价：

2+2+3+5=\boxed{12}

五座城镇全部连通，并且没有环。这就是本例的最小生成树。

第四幕：为什么贪心不会犯错？真正重要的是数学证明

你可能会提出一个非常合理的反对意见：“只选择眼前最便宜的线路，怎么保证未来不会后悔？”这个问题问到了贪心算法的核心。事实上，许多贪心策略确实会犯错。但最小生成树问题具有一种特殊的数学性质。叫作：切分性质（Cut Property）。假设我们把所有顶点分成两个互不重叠的集合：

S,\quad V-S

所有跨越这两个集合的边，叫作跨越这个切分的边。如果我们必须把两个集合连接起来，就至少需要一条跨越切分的边。那么，自然应该优先考虑其中最便宜的那条。更严格地说：对于与当前已选安全边相容的切分，跨越该切分的一条最小权重边，是安全的选择：它可以属于某棵最小生成树。这就是 Kruskal、Prim 和 Borůvka 能够工作的共同数学基础。^{[Network Optimization · Fabio Furini]}

为什么成立？一个交换论证

假设有一棵最小生成树

T

，但它没有选择某条安全的最便宜跨切分边

e

。如果把

e

加进去，就会形成一个环。这个环必然还包含另一条跨越相同切分的边

f

。由于

e

是该切分中最便宜的边：

w(e)\leq w(f)

现在把

f

删除，再保留

e

。新结构仍然连通、无环。而且：

w(T')=w(T)+w(e)-w(f)\leq w(T)

如果原来的

T

已经是最优的，那么新树也能保持最优。所以，选择

e

不会让我们失去获得某棵最小生成树的机会。这就是贪心正确性的数学基础。它不是因为“便宜看起来合理”，而是因为我们能够证明：即使当前选择与某个最优方案不同，也能通过交换，把它改造成一个不更差的最优方案。这种证明方法叫作 Exchange Argument（交换论证）。以后遇到新的贪心题目，你可以主动寻找这种结构。

第五幕：1930年，一封写给 Borůvka 的信，提出了另一种方案

故事并没有在1926年结束。Borůvka 发表论文之后，他的一位数学家同事 Vojtěch Jarník 研究了同一个问题。1929年前后，Jarník 在写给 Borůvka 的信中介绍了自己的方法。1930年，他正式发表相关论文。这是一段很有意思的历史。因为今天大量算法教材把这种方法称为 Prim 算法。但它在 Prim 发表相关论文之前27年，就已经由 Jarník 研究并发表了。^{[DML-CZ][DML-CZ]}

Jarník 的想法与 Borůvka 有什么不同？

Borůvka 算法让各个独立分量同时寻找便宜的外部连接。而 Jarník 的方法更加集中。从一个顶点开始。维持一棵已经连通的树。每次选择从这棵树通向外部的最便宜边。于是，这棵树不断向外生长。这就是今天常称的 Prim–Jarník 算法。例如，从 A 开始。最便宜的外部线路是：A—B，成本2。此时已连接 A、B。下一步，不能只查看 B 的邻居。而必须检查从整个集合 {A,B} 通向外部的所有候选线路。其中 A—D 成本3，是当前最便宜的可用跨界线路。因此加入 D。接下来继续选择跨越已连接集合与未连接集合的最低成本线路。直到连接全部顶点。

1957年：贝尔实验室的重新发现

Robert C. Prim

1921—2021 · 美国数学家、计算机科学家曾在贝尔实验室从事网络设计和组合优化研究，后来参与计算机科学与通信技术方面的工作。

1957年11月，Prim 在 Bell System Technical Journal 发表：Shortest Connection Networks and Some Generalizations《最短连接网络及其若干推广》。论文明确讨论如何以最小的总线路长度连接一组终端，并介绍可用于实际图形设计和计算过程的方法。论文还引用了 Kruskal 1956年的研究和 Borůvka 1926年的论文。^{[Wiley Online Library]}Prim 1957年原始论文为什么这一方法在英文算法教材里更经常叫作 Prim 算法，而不是 Jarník 算法？主要与学术成果在不同语言、研究机构和学术圈中的传播有关。Jarník 的论文以捷克语发表，而 Prim 的论文出现在影响力较大的英文通信技术期刊中。这并不意味着 Prim 故意隐瞒前人的成果，也不能简单用一个单一原因解释命名过程。但从今天更完整的科学史角度看，称它为Jarník–Prim 算法，能够更准确地体现两人的历史贡献。

一个出人意料的交叉

还记得第六章最短路径故事里的 Edsger W. Dijkstra 吗？他在1959年的图算法论文中，也描述了相近的最小生成树构造方法。于是，一个数学思想在不同时代、不同研究环境下被反复发现和传播。这在算法史中非常普遍。

第六幕：Kruskal 与 Prim，到底谁更聪明？

现在我们把两种方法放到一起比较。

Kruskal

像建设多个小村庄之间的道路网络。一开始，每个城镇独立。按照线路成本，从便宜到昂贵，逐步合并不同网络。

Prim–Jarník

像一棵从中心逐渐向外生长的树。从一个城镇出发，不断选择连接已建网络与外部城镇的最便宜线路。

两者的共同点：都是贪心算法，都能够产生最小生成树。但它们维护的中间状态不同。

特点	Kruskal	Prim–Jarník
初始状态	每个顶点独立	从一个起点出发
每步选择	全局最便宜且不形成环的边	当前树通向外部的最便宜边
常用数据结构	排序 + 并查集	优先队列
常见复杂度	$O(E\log E)$	$O(E\log V)$
适用思路	逐步合并连通分量	不断扩展一棵树

两者的具体性能还取决于图的稠密程度和实现方式。

Kruskal 为什么需要并查集？

假设当前已经选择若干条边。现在准备加入 A—D。我们必须判断：A 和 D 是否已经通过其他边连通？如果已经连通，再加入就会形成环。每次都使用 DFS 检查当然可以，但在大量边的情况下，效率可能并不理想。于是，我们可以使用一种新的数据结构：并查集（Disjoint Set Union，DSU）。它主要支持两个操作。find(x)：找出 x 所属集合的代表。union(a,b)：将两个集合合并。通过路径压缩和按秩或按大小合并，它能够以非常接近常数的摊还时间完成操作。这使 Kruskal 算法的主要开销通常落在边排序上。

Python：Kruskal 的完整实现

def kruskal(vertices, edges):
    parent = {v: v for v in vertices}
    size = {v: 1 for v in vertices}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(a, b):
        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

    mst = []
    total = 0

    for a, b, weight in sorted(
        edges, key=lambda e: e[2]
    ):
        if union(a, b):
            mst.append((a, b, weight))
            total += weight

            if len(mst) == len(vertices) - 1:
                break

    return mst, total

这里 union() 的返回值很重要。如果两个顶点已经在同一个集合中，它返回 False。这代表：加入该边将形成环，因此必须拒绝。如果它们属于不同集合，则合并并接受该边。这段代码还展示了一个与我们前面课程的重要联系：

第七章的排序算法，用于把边按权重排列。
第六章的图论，用于表示网络。
第五章的树思想，帮助理解连通分量和森林。
现在的并查集，负责快速判断是否产生环。

这些知识终于组合成了一个完整的算法系统。

第七幕：贪心算法也有骗局

到这里，你可能产生一个危险的想法：“既然每次选择最便宜的线路能够得到全局最优，那么其他问题也可以这么做吧？”不一定。事实上，贪心算法最大的陷阱，就是它看起来往往非常合理。我们用一个简单的找零钱问题来体验。假设你有三种硬币：1元、3元、4元你需要凑出6元。如果使用贪心：每次选择当前不超过剩余金额的最大面额。首先选择4元。剩余2元。只能再选择两个1元。于是得到：4 + 1 + 1一共3枚硬币。但实际上：3 + 3只需要2枚。贪心失败了。

实验二：贪心与动态规划的正面对决

找零钱实验室

硬币面额：1、3、4

Greedy vs DP

目标金额

6

贪心算法3 枚

动态规划2 枚

贪心失败！贪心用了 3 枚硬币，但动态规划只需要 2 枚。局部最大面额的选择破坏了全局最优。

为什么最小生成树可以贪心，找零钱却不一定？因为我们不能只凭“眼前最便宜”或“眼前最大”来判断。最小生成树具有切分性质和交换论证。而一般的硬币系统并不保证类似性质。这就是贪心算法真正需要学习的地方：不是学会挑最小值，而是学会证明局部选择为什么不会破坏全局最优。

第八幕：1926年的电网问题，为什么会影响今天的计算机？

回到 Borůvka 的时代。当时他研究的是如何经济地连接城镇。但后来，数学家和工程师发现，这一问题具有远远超出电网的应用价值。

通信网络

如果需要用有成本的链路把多个站点连接起来，最小生成树可以提供一种最低总连接成本的基础网络结构。不过，真实通信网络还需要考虑冗余、带宽、延迟和故障容忍，因此实际工程通常不会只依赖一棵没有冗余的生成树。

数据聚类

在机器学习和数据分析中，可以把数据点看成顶点，把相似性或距离看成边权。构造最小生成树后，删除其中较长的边，可能把数据划分成不同簇。这是单链接层次聚类（Single-linkage Clustering）的一种重要解释方式。

图像分割

在某些经典图像处理算法中，图像像素或区域可以被视为顶点。像素之间的颜色差异或特征距离，构成边权。通过图的连通性、生成树或森林，可以研究怎样把图像划分成不同区域。

软件与算法工程

今天，当你编写最小生成树算法时，还会遇到排序、优先队列、并查集和图遍历。这些结构也是现代大型软件系统反复使用的基础组件。正因如此，Kruskal 算法不仅是一道经典编程题，更是一次把多种数据结构组合成完整解决方案的训练。

第九幕：四位研究者，三种不同的贪心思路

这一章最值得记住的历史，并不是“1956年 Kruskal 发明了最小生成树”。因为那不符合完整史实。真正的发展线索是：

1926年 · Borůvka从摩拉维亚地区的电气化问题出发，提出让各个连通分量选择最低成本外部连接、逐轮合并的算法。

1930年 · Jarník发展出从一个起点不断扩展连通树的算法，并在写给 Borůvka 的信中讨论这一方法。

1956年 · Kruskal按边权从小到大逐步构造无环森林，在一篇三页论文中提出了极为简洁的生成树方法。

1957年 · Prim在通信网络研究中发表最短连接网络的方法，使相关算法获得更广泛的英文传播与工程关注。

四位研究者的贡献共同展示了一段值得回味的科学史。有些数学方法，是由现实工程问题直接推动的。有些方法，会在不同年代被独立重新发现。还有些方法，虽然很早就已经出现，却因为语言和学术传播的差异，没有立刻得到广泛关注。科学发展的真实过程，远比“某年某人突然发明某算法”更加复杂。

终章挑战：你能证明一次贪心选择是安全的吗？

现在，我们把视线从电网移开。假设有三项工作：

工作	开始时间	结束时间
A	1	4
B	2	3
C	3	5

同一时间只能执行一项工作。区间采用左闭右开形式，因此一个任务在3结束，另一个任务可以在3开始。你的目标是：完成尽可能多的任务，而不是让总工作时间最长。如果你先选择 A，那么 B 和 C 都会与 A 冲突。只能完成1项任务。如果你先选择结束最早的 B，再选择 C，那么能够完成2项任务。这引出了另一种经典贪心策略：活动选择问题中，优先选择结束时间最早的兼容活动，可以获得最多的活动数量。原因在于，较早结束的活动通常能为后续活动保留更多时间；通过交换论证可以严格证明这一策略的正确性。它与最小生成树的切分性质不同，但背后具有相近的数学精神。那就是：寻找一个可以证明安全的局部选择，并在做出选择后缩小剩余问题。

尾声：贪心，不是短视，而是有证据的果断

1926年，Otakar Borůvka 面对一个实际的电力网络问题。他的算法让不同连通分量不断选择便宜的外部线路。1930年，Jarník 提出从一棵树不断向外扩展的另一种方法。1956年，Kruskal 将按照边权排序、避免成环的思想写成短短几页论文。1957年，Prim 则从通信网络连接问题出发，推动了这一类算法的发展。他们使用的具体方法并不完全相同。但共同的数学原则是：不必穷举所有完整方案。只要能够证明某一步选择是安全的，就可以果断地做出决定，并继续解决剩下的问题。这就是贪心算法真正迷人的地方。

本章最应该掌握的内容

概念	核心思想
Greedy Algorithm	每一步进行局部最优选择
Minimum Spanning Tree	以最低总权重连接全部顶点
Borůvka	各连通分量同时选择最低成本外部边
Kruskal	按权重选边，避免形成环
Prim–Jarník	从一棵树不断扩展
Cut Property	某些最低权重跨切分边是安全选择
Exchange Argument	通过替换最优方案中的部分选择来证明正确性
Disjoint Set Union	高效管理连通分量与判断环

历史延伸阅读

这一章值得保留的原始与学术资料有：Borůvka 1926年两篇论文的英文翻译与历史评论，可看到最小生成树在摩拉维亚电气化问题中的真实起源。《A Few Remarks on the History of MST-Problem》，介绍 Borůvka、Jarník 与后来研究者之间的发展脉络。Kruskal 1956年原始论文 PDF，可以直接看到他如何描述按最短边构造生成树。Prim 1957年原始论文，展示通信网络背景下的最短连接算法研究。

下一章预告

第十章：回溯算法——为什么计算机要学会承认自己走错了路？

1848年，一位德国棋手研究一个问题：在国际象棋棋盘上放置八个皇后，使它们彼此无法攻击，究竟有多少种摆法？后来，数学家 Carl Friedrich Gauss 也参与过这个问题的讨论。这就是著名的八皇后问题。它看起来只是一个有趣的棋盘谜题，却逐渐成为回溯搜索的经典例子。下一章，我们将从八皇后问题的早期历史出发，了解计算机怎样通过“尝试—检查—撤销—再尝试”系统地搜索解空间，以及为什么适时放弃一条错误路线，反而可以节省大量计算。而我们最想研究的问题是：既然计算机的速度那么快，为什么有时不应该继续尝试，而应该立即后退？