第 06 章

七座桥与一杯咖啡——人类如何发明寻找最短路径的算法？

正在加载交互实验…

历史跨度：1735—1959年

本章主角：Leonhard Euler、Charles Pierre Trémaux、Edward F. Moore、Edsger W. Dijkstra

1735年，一位28岁的数学家面对一道城市居民争论不休的难题。

他没有尝试走遍所有路线，而是证明：无论怎样走，都不可能成功。

221年后，一名26岁的年轻计算机科学家坐在阿姆斯特丹的一家露天咖啡馆里。

他与未婚妻逛街逛累了，坐下来喝杯咖啡。

大约20分钟后，他想出了一种寻找最短路径的算法。

这个算法后来以他的名字命名，成为现代计算机科学中最著名的算法之一。

这两个故事有一个共同的主题：

当道路变得复杂时，真正重要的也许不是寻找路线，而是找到一种能够理解道路的方法。

序幕：1735年，普鲁士的一座城市

18世纪，欧洲东部有一座繁华的城市。

它叫柯尼斯堡（Königsberg）。

当时属于普鲁士王国，今天这座城市叫加里宁格勒，位于俄罗斯。

一条名叫普雷格尔河（Pregel）的河流穿过城市，将其分割成几片陆地。

河流上有两座重要的岛屿。

七座桥梁把这些区域连接起来。

城市里的居民面对一个有趣的问题：

能否从城市某处出发，跨过全部七座桥，每座桥恰好经过一次？

你可以在任何地方出发，也不要求回到起点。

唯一的限制是：

每座桥只能走一次，而且七座桥都必须经过。

这个问题看起来很简单。

你可能拿出纸笔，画出城市地图，然后开始尝试。

走第一座桥。

再走第二座桥。

接着选择第三座桥……

可是不管怎样调整路线，似乎总会遇到一座无法经过的桥。

但是，没有找到路线，并不意味着路线不存在。

也许只是你的方法不够聪明。

这正是数学与普通猜谜游戏之间一个非常重要的区别。

数学家不仅想知道答案，还想证明答案为什么必然成立。

于是，一位年轻数学家登场了。

第一幕：欧拉——一个差点没有成为数学家的天才

Leonhard Euler（莱昂哈德·欧拉）

1707—1783年

瑞士数学家、物理学家，18世纪最伟大的数学家之一。

欧拉1707年出生于瑞士巴塞尔。

他的父亲 Paul Euler 是一位牧师，希望儿子以后也能从事宗教工作。

但年轻的欧拉很早就表现出了出色的数学才能。

13岁时，他进入巴塞尔大学学习。

在那里，他认识了一位后来对自己影响深远的老师：

Johann Bernoulli（约翰·伯努利）。

伯努利家族在数学史上非常著名。

Johann Bernoulli 是当时欧洲顶尖的数学家之一。

他发现欧拉具有非同寻常的数学天赋，并给予指导。

欧拉后来逐渐走上数学研究道路。

1727年，年仅20岁的欧拉前往俄国圣彼得堡科学院工作。

此后，他在数学、力学、数论、天文学等领域留下了大量成果。

但是，我们今天的故事不是关于复杂的微积分。

而是一座城市的七座桥。

1. 欧拉收到了一道特殊的难题

1735年前后，欧拉开始研究柯尼斯堡七桥问题。

历史资料表明，他曾与研究者 Carl Leonhard Gottlieb Ehler 等人通信讨论此事。

1735年8月，欧拉向圣彼得堡科学院介绍了自己的研究结果。

随后，他在1736年写成论文：

Solutio problematis ad geometriam situs pertinentis

中文可以译为：

《一个与位置几何有关的问题的解答》。

这篇论文后来成为图论历史上最重要的早期文献之一。^{(PDF) About the cover: Euler and Königsberg’s Bridges: A historical view · Topology history - MacTutor History of Mathematics}

特别有意思的是：

欧拉最初并没有把这个问题当成通常意义上的几何计算题。

因为它不需要计算桥梁长度。

不需要测量河流宽度。

也不需要知道城市面积。

事实上，地图画得再精确，也不会让答案变得更容易。

欧拉意识到了这一点。

于是，他开始舍弃不重要的信息。

这一次抽象，改变了数学的发展方向。

第二幕：欧拉做了一件不可思议的事——把整座城市删除

想象一下：

你现在是欧拉。

面前放着一张柯尼斯堡地图。

河流、建筑、道路、桥梁，全部清清楚楚。

可是，欧拉发现一个问题。

我们真正关心的只有：

有哪些陆地区域？
哪些区域之间存在桥梁？

至于桥梁长什么样、建筑在哪儿，完全无关紧要。

于是，我们把地图简化。

将四片陆地标记为：

A、B、C、D。

每片陆地画成一个点。

每座桥画成连接两个点的一条线。

得到这样的结构：

        C
       /|\
      / | \
     A--|--D
      \ | /
       \|/
        B

上图仅示意点与连线的概念，不能精确表示七桥之间的全部重边关系。

我们用下面的边列表，准确表示原问题的一种等价编号方式：

A — B    两座桥
A — C    两座桥
A — D    一座桥
B — D    一座桥
C — D    一座桥

一共七条边。

注意：

A 和 B 之间可以有两条不同的边。

在图论中，这种允许两个顶点之间存在多条边的结构，叫作多重图（Multigraph）。

现在，一座复杂的城市被变成了：

四个顶点，七条边。

这就是图（Graph）。

数学上一般表示为：

$G=(V,E)$

其中：

$V$ ：顶点集合（Vertices）。
$E$ ：边集合（Edges）。

对于当前问题：

$V={A,B,C,D}$

而七座桥构成七条边。

你可能觉得这种抽象非常自然。

但在1735年，研究抽象连接关系本身，还没有形成今天这样成熟的图论体系。

欧拉的贡献就在于：

他把一个具体的地理问题，转化成了只研究连接关系的数学问题。

而这也成为现代计算机科学最重要的思维方式之一。

第三幕：为什么七座桥根本不可能走完？

现在，我们终于可以解决问题了。

不过，我希望你先不要看答案。

假设你正在图中的一个顶点。

你通过一座桥进入某片陆地。

如果这片陆地不是路线的终点，那么你接下来必须通过另一座尚未走过的桥离开。

也就是说：

每次进入，通常必须对应一次离开。

于是，经过中间区域的桥梁，总是一进一出，成对出现。

这就引出了一个数学概念：

度（Degree）

一个顶点连接了多少条边，称为这个顶点的度。

注意，多重图中的平行边要分别计算。

根据刚才的七桥结构：

顶点	连接的桥数	度
A	5	5
B	3	3
C	3	3
D	3	3

四个顶点的度全部是奇数！

这意味着什么？

假设一条路线经过每条边恰好一次。

对于既不是起点也不是终点的顶点，每次进入都必须离开，所以它连接的已使用边必须成对。

因此，这些中间顶点的度必须是偶数。

只有起点和终点可以例外。

因为起点可能多一次离开。

终点可能多一次进入。

所以：

一条经过所有边且每条边恰好一次的开放路径，最多只能有两个奇数度顶点。

但柯尼斯堡有四个！

因此：

$\boxed{\text{不存在满足要求的路线}}$

问题解决了。

没有穷举。

没有试错。

也没有寻找所谓更聪明的路线。

我们只是发现了一条所有合法路线都必须遵守的规则。

然后证明原问题违反了这条规则。

这是一种非常强大的算法思想：

在开始搜索之前，先判断问题是否具有解。

欧拉路径与欧拉回路

现代图论把这些问题进行了系统化。

对于忽略孤立顶点后连通的无向图：

奇数度顶点数	结论
0	存在欧拉回路
2	存在开放的欧拉路径
4个或更多	不存在欧拉路径

其中：

欧拉路径（Eulerian Trail）：每条边恰好经过一次。

欧拉回路（Eulerian Circuit）：经过每条边恰好一次，并回到起点。

注意，欧拉问题关注的是边，不是顶点。

这一区别非常重要。

顺带说一句，现代研究者在重新分析欧拉原始论文时，也指出其关于不可能性的证明成立，而某些存在性情形的论证还不完全符合现代严格证明的标准。科学史上的伟大发现也可以被后来者进一步完善。^{Euler and the Bridges of Königsberg | A History of Mathematical Impossibility | Oxford Academic}

第四幕：一个数学问题，为什么会改变两百年后的计算机世界？

欧拉并不知道，两百多年之后，程序员会把他的抽象思想用于数以亿计的计算设备。

但请想一想：

互联网是什么？

无数计算机通过网络连接起来。

地图导航是什么？

无数路口通过道路连接起来。

社交网络是什么？

无数用户通过关注、好友等关系连接起来。

围棋棋盘上的相邻交叉点，也可以用图的顶点和边来描述。

这些事物表面上没有任何共同之处。

但如果去掉不重要的细节，就会发现：

它们都可以表示为：

$G=(V,E)$

这就是图论的力量。

它不关心一个点究竟代表城市、计算机还是人。

它只关心点与点之间的关系。

然而，仅仅知道图的结构，还不够。

到了19世纪，研究者开始面对新的问题：

如果一张图非常复杂，怎样系统地探索它？

第五幕：19世纪，一位法国工程师开始研究迷宫

故事的第二位重要人物是：

Charles Pierre Trémaux（特雷莫）。

他是一位法国工程师。

19世纪，Trémaux 提出了一种系统探索迷宫的方法。

这套方法通过标记已经走过的通道，避免在复杂迷宫中无限兜圈子。

它后来经数学家 Édouard Lucas 等人的介绍而广为人知。

今天，我们通常把 Trémaux 的迷宫探索方法视为深度优先搜索思想的重要历史先驱。

不过，不能把现代计算机中的完整 DFS 实现直接说成由他发明。两者之间经历了进一步的数学形式化和程序设计发展。

1. 假设你进入一座巨大迷宫

你站在入口。

面前有三条路：

你会怎样探索？

一种策略是：

从 A 出发，先走 B。

到达 B 之后，继续选择 E。

如果 E 没有其他道路，就返回 B。

然后探索 F。

B 的所有道路都探索完之后，再回到 A。

接着探索 C、D。

得到顺序：

A → B → E → F → C → D

这就是深度优先搜索：

Depth-First Search，DFS。

它的核心不是找到某条特定路线，而是：

沿一个方向尽可能深入，走不通后再回溯。

熟悉吗？

这正是第二章学过的：

栈与递归！

DFS 为什么适合使用栈？

因为当你从 A 进入 B，再从 B 进入 E 时，必须记住：

E 探索结束后，要回到 B。

B 探索结束后，要回到 A。

最后进入的节点，最先完成回退。

这就是 LIFO，后进先出。

def dfs(graph, start):
    visited = set()

    def visit(node):
        visited.add(node)
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visit(neighbor)

    visit(start)

对于使用邻接表表示的图，DFS 的时间复杂度为：

$O(V+E)$

其中 $V$ 为顶点数， $E$ 为边数。

不过，有一个需要注意的限制：

DFS 不保证在无权图中找到最短路径。

它可能沿着一条很长的路线走到底，才发现另一条更短的道路。

那么，如果我们想找到最短路径，应该怎么办？

1959年，一位美国数学家给出了重要答案。

第六幕：1959年，Moore 让迷宫探索变成一圈圈扩散

这位研究者是：

Edward F. Moore（1925—2003）。

他曾在贝尔实验室工作，在自动机理论、计算理论等领域作出了重要贡献。

1959年，他发表了一篇论文：

The Shortest Path Through a Maze

《穿越迷宫的最短路径》。

这篇论文是现代广度优先搜索与无权图最短路径历史上的重要文献。

Moore 的研究与此前的迷宫探索思想存在历史联系，但现代 BFS 也不是凭空从这一篇论文开始的。

我们现在从问题本身重新推导它。

1. 怎样保证找到最短路线？

假设你站在迷宫入口 A。

你有两种选择。

第一种：沿一条路不断深入。

第二种：先探索距离入口一步的位置，再探索距离入口两步的位置，以此类推。

如果每条边的距离都相同，哪一种策略更容易保证最短路径？

答案显然是第二种。

因为只要你按照距离由近到远的顺序探索，那么第一次到达目标时，就已经找到了最少边数的路线。

这就是：

Breadth-First Search，BFS。

广度优先搜索的基本过程

假设有这样一张图：

从 A 开始。

第一层：

第二层：

B、C

第三层：

D、E、F

第四层：

访问顺序可以是：

A → B → C → D → E → F → G

现在回忆第三章。

当时我们讲过哪一种数据结构？

没错。

队列。

BFS 使用 FIFO 规则，让先发现的节点优先被探索。

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

时间复杂度同样是：

$O(V+E)$

这时你应该注意到一个非常深刻的现象：

DFS 和 BFS 的时间复杂度可以完全一样，但它们的行为却截然不同。

原因不是遍历了不同数量级的数据。

而是它们管理待处理节点的方式不同。

比较	DFS	BFS
核心结构	栈	队列
探索方式	尽量深入	逐层扩散
无权图最短路径	不保证	保证
时间复杂度	O(V+E)	O(V+E)

这就是为什么我们之前学习栈和队列不是孤立的知识点。

它们会直接决定算法的搜索策略。

不过，BFS 仍然存在一个限制。

如果道路长度不同呢？

例如，从 A 到 B 是100公里，从 A 到 C 只有2公里。

BFS 只关心经过多少条边，并不知道道路长度。

因此，我们需要一种新的算法。

这时，故事来到1956年的荷兰。

第七幕：1956年，阿姆斯特丹的一杯咖啡

Edsger Wybe Dijkstra（艾兹赫尔·戴克斯特拉）

1930—2002年

荷兰计算机科学家。

这是本章最精彩的一段真实历史。

Dijkstra 于1930年出生于荷兰鹿特丹。

他最初学习数学和理论物理。

1952年，他开始在阿姆斯特丹的数学中心（Mathematisch Centrum）从事程序设计工作。

当时，程序员还不是一个成熟的职业。

甚至连“程序设计究竟算不算真正的科学”这样的问题，也没有得到普遍认同。

Dijkstra 后来回忆，自己早年就职登记时，连正式填写什么职业都成了一个问题。

他选择了程序设计这条道路。

而这条道路最终将改变计算机科学的发展。

1. 一台新计算机需要一个精彩的演示

1956年，荷兰数学中心研制的 ARMAC 计算机准备正式亮相。

ARMAC 是：

Automatische Rekenmachine MAthematisch Centrum

即数学中心自动计算机。

Dijkstra 希望设计一个普通观众也能理解的演示程序。

单纯让计算机计算复杂公式，观众可能并不感兴趣。

但如果计算机能够回答：

“从鹿特丹到格罗宁根，应该怎样走才最短？”

那就完全不同了。

任何人都能理解这个问题。

于是，Dijkstra 开始思考最短路径算法。

这段故事不是后人编造的。

在多年后的采访与个人回忆中，他亲自讲述过这件事。

2. 那杯著名的咖啡

Dijkstra 在接受《Communications of the ACM》的采访时回忆：

一天上午，他和当时的未婚妻在阿姆斯特丹逛街。

两人走累了。

于是，他们坐在一家露天咖啡馆里休息。

喝咖啡的时候，Dijkstra 开始思考如何寻找城市之间的最短路线。

大约20分钟后，他想出了核心算法。

他后来特别强调了一件事：

整个思考过程没有使用纸笔。

他认为，这反而迫使自己避免不必要的复杂性。

这不是说算法实现与证明都在20分钟内彻底完成，而是指最初的核心思想在那段短暂的思考中形成。

这段回忆可以在他的个人档案以及后来的访谈中找到。^{E.W.Dijkstra Archive: "From my Life" (EWD 1166) · (PDF) An Interview with Edsger W. Dijkstra · Edsger W. Dijkstra: Brilliant, colourful, and opinionated}

而最令人意外的是：

Dijkstra 当时并没有意识到，这个算法会变得如此重要。

他最初只是想为一台计算机设计一个演示程序。

1956年提出算法后，他直到1959年才发表相关论文：

A Note on Two Problems in Connexion with Graphs

《有关图的两个问题的一则札记》。

论文只有短短几页。

其中一个问题涉及最短路径，另一个涉及最小生成树。

Dijkstra 后来回忆，当时离散算法尚未获得足够的数学地位，也缺少合适的发表渠道。^{E.W.Dijkstra Archive: "From my Life" (EWD 1166) · In Memoriam: Edsger W. Dijkstra}

现在，我们来看看那杯咖啡背后究竟藏着什么思想。

第八幕：Dijkstra 如何在20分钟里想出最短路径算法？

先忘记1956年的咖啡馆。

我们直接进入问题。

假设有五座城市：

        4
   A -------- B
   |          |
  2|          |5
   |    1     |
   C -------- D
    \        /
     \3    /2
      \   /
        E

为了避免图形排版造成歧义，我们明确列出道路：

道路	距离
A—B	4
A—C	2
C—D	1
B—D	5
C—E	3
D—E	2

问题：

从 A 到 E，最短的路线是什么？

你可能首先想到：

A → C → E

距离：

$2+3=5$

再看看：

A → C → D → E

距离：

$2+1+2=5$

也是5。

而 A → B → D → E：

$4+5+2=11$

明显更长。

但是，如果有100万座城市呢？

你不可能手工比较所有路线。

我们需要一套系统的方法。

1. Dijkstra 的第一个关键思想

从起点 A 出发。

首先确定：

$dist(A)=0$

其他城市距离暂时不知道：

$dist(B)=dist(C)=dist(D)=dist(E)=\infty$

然后探索 A 的邻居。

可以直接得到：

$dist(B)=4$

$dist(C)=2$

现在面临一个选择：

先处理 B，还是 C？

Dijkstra 的核心策略是：

总是优先选择当前暂定距离最小、尚未确定的节点。

因此，我们先选择 C。

因为：

$2<4$

这一步就是整个算法最关键的贪心选择。

2. 为什么先处理 C？

因为所有道路长度都非负。

当前从 A 到 C 的已知距离是2。

而其他尚未确定的节点，暂定距离至少也是2。

如果想通过其他节点绕路再到 C，只会增加非负的道路代价，不可能得到一条比2更短的路线。

所以，我们可以确定：

$dist(C)=2$

这是最终答案。

这种思想叫作：

Greedy Algorithm，贪心算法。

每次选择当前最有希望的候选节点，并利用问题性质证明这个选择不会出错。

注意，这里“证明不会出错”的关键条件是：

边权不能为负。

如果允许负权边，某个已经确定的最短距离可能在后来被进一步降低，普通 Dijkstra 算法便不再适用。

第九幕：亲手执行一次 Dijkstra 算法

现在我们进行一次完整推演。

初始状态：

节点	暂定距离
A	0
B	∞
C	∞
D	∞
E	∞

第一步：处理 A

从 A 可以到达 B 和 C。

更新：

节点	暂定距离
A	0
B	4
C	2
D	∞
E	∞

A 已经确定。

第二步：处理 C

未确定节点中，C 的暂定距离最小，为2。

从 C 出发：

到 D：

$2+1=3$

到 E：

$2+3=5$

更新：

节点	暂定距离
A	0
B	4
C	2
D	3
E	5

C 已经确定。

第三步：处理 D

剩下未确定的节点：

B = 4，D = 3，E = 5。

选择 D。

从 D 到 E：

$3+2=5$

原来 E 的距离也是5。

因此，E 不需要更新。

从 D 到 B：

$3+5=8$

比 B 原来的4更长，也不更新。

第四步：处理 B

B 的距离为4。

从 B 出发不会找到更短的路线。

因此，B 也被确定。

第五步：处理 E

E 的距离为5。

所有节点处理完毕。

最终结果：

城市	从 A 出发的最短距离
A	0
B	4
C	2
D	3
E	5

从 A 到 E 的最短距离是：

$\boxed{5}$

而且存在两条同样短的路线：

A → C → E

以及：

A → C → D → E

这说明最短路径不一定唯一。

第十幕：为什么这与 BFS 看起来如此相似？

现在，我们把前面两种算法放在一起。

BFS：

每次从普通队列中取出最早发现的节点。

Dijkstra：

每次取出当前暂定距离最小的节点。

有没有发现：

它们都在不断探索邻居，都要维护待处理节点。

真正的不同是：

BFS 使用普通队列。

Dijkstra 通常使用优先队列。

为什么优先队列重要？

假设当前有四个候选节点：

节点	暂定距离
A	12
B	5
C	20
D	3

如果使用普通 FIFO 队列，先进入的节点先处理。

但 Dijkstra 要求先处理 D。

因为它的距离最小。

接下来处理 B。

然后 A。

最后 C。

这种每次能够快速取出最小元素的数据结构，可以使用：

最小堆（Min Heap）。

而最小堆又是一种特殊的二叉树！

你看，前几章的知识再次连起来了。

数组、树、队列、图，并不是互不相关的概念。

它们会组合成更复杂的算法。

Dijkstra 的 Python 实现

import heapq

def dijkstra(graph, start):
    distances = {
        node: float("inf")
        for node in graph
    }

    distances[start] = 0

    pq = [(0, start)]

    while pq:
        current_dist, node = heapq.heappop(pq)

        if current_dist > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            new_dist = current_dist + weight

            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist

                heapq.heappush(
                    pq,
                    (new_dist, neighbor)
                )

    return distances

这里 heapq 实现了最小堆功能。

每次弹出的，都是当前优先级最小的元素。

但要注意：

这段代码要求边权非负，且图中每个被访问的顶点都作为 graph 的键出现。

如果想恢复具体最短路线，还需要保存每次更新时的前驱节点。

时间复杂度

使用邻接表和二叉堆，并允许向堆中重复插入更新后的候选距离时，常见复杂度上界为：

$O((V+E)\log V)$

如果使用更简单的数组，每次线性扫描寻找最小距离节点，则可以达到：

$O(V^2+E)$

因此，不同的数据结构实现，会影响同一个算法的实际性能。

第十一幕：一次改变历史的思想——最短路径不一定需要搜索全部路线

回顾 Dijkstra 的方法。

它没有列出所有可能路线。

而是不断维护：

从起点到各节点，目前已知的最短距离。

然后每次选择距离最小的候选节点，将其最终确定。

这是一种非常漂亮的数学构造。

它的正确性来自非负权重条件下的贪心选择性质。

而算法的强大之处在于：

即使图中存在大量可能的路径，我们也不必枚举所有路径。

因为那些不可能优于当前结果的路线，可以被提前排除。

这和欧拉当年的七桥问题，竟然有某种思想上的相似性。

欧拉没有穷举所有走法，而是发现了一条必要条件。

Dijkstra 也没有穷举所有路线，而是发现了能够安全确定最短距离的条件。

他们都通过数学结构，避免了无意义的搜索。

第十二幕：从1735年的七座桥，到今天的互联网

现在，让我们看看图论在现代软件中究竟有多重要。

1. 地图导航

道路可以表示为边。

城市或路口可以表示为顶点。

边权可以表示距离、通行时间或其他成本。

这就形成了一张加权图。

现代导航系统还要考虑实时交通、转弯限制、道路等级等因素，因此通常会采用比基础 Dijkstra 更复杂的算法和工程优化。

但图搜索仍然是它们的重要数学基础。

2. 网络路由

互联网可以表示为由路由器与链路组成的图。

网络路由协议需要决定数据包应当如何到达目标。

例如，OSPF 使用链路状态信息，并基于最短路径优先（SPF）计算路由。

其核心算法与 Dijkstra 最短路径思想密切相关。

3. 游戏 AI

游戏中的角色需要在地图中寻找道路。

例如：

玩家 A
   |
   +--- 障碍物
   |
   +--- 通道
   |
目标 B

游戏 AI 可以把可通行区域转换为图，然后使用 BFS、Dijkstra 或 A* 等算法寻找路线。

如果每次移动代价相同，BFS 就可能足够。

如果不同地形具有不同的移动成本，就需要加权最短路径算法。

如果我们还知道目标的方向或距离估计，就可以进一步研究 A*。

4. 围棋中的连通关系

围棋同样可以用图来理解。

棋盘上的交叉点作为顶点。

水平、垂直相邻的交叉点之间存在边。

相同颜色的棋子通过相邻关系形成连通块。

判断一块棋的组成，可以利用 DFS 或 BFS。

例如：

def find_group(board, x, y):
    color = board[x][y]

    stack = [(x, y)]
    visited = set()

    while stack:
        cx, cy = stack.pop()

        if (cx, cy) in visited:
            continue

        visited.add((cx, cy))

        for nx, ny in neighbors(cx, cy):
            if board[nx][ny] == color:
                stack.append((nx, ny))

    return visited

这是一个简化示例，假设 neighbors() 只返回棋盘范围内的合法邻点，并且起始位置存在棋子。

你会发现：

从1735年的桥梁，到现代围棋程序中的棋块搜索，背后竟然可以使用同一种数学抽象。

第十三幕：我们终于可以把前六章连接起来了

回顾一下已经学习过的数据结构。

章节	数据结构 / 算法	解决的问题
第一章	数组、链表	怎样组织数据
第二章	栈、递归	怎样管理嵌套任务
第三章	队列	怎样按照顺序处理任务
第四章	哈希表	怎样快速定位数据
第五章	树	怎样组织动态有序数据
第六章	图	怎样表示复杂连接关系

到了今天，你已经接触了计算机科学中最重要的一批基础数据结构。

它们的关系其实非常紧密：

图 Graph
    |
    +--- DFS
    |     |
    |     +--- 栈 Stack
    |     |
    |     +--- 递归 Recursion
    |
    +--- BFS
    |     |
    |     +--- 队列 Queue
    |
    +--- Dijkstra
          |
          +--- 优先队列
                  |
                  +--- 最小堆
                          |
                          +--- 二叉树

这张关系图说明：

计算机科学的很多复杂算法，并不是从零创造一个全新的世界。

而是把早已掌握的基础思想，以新的方式组合起来。

终章挑战：假如你是1956年的 Dijkstra

现在，我们进行一次真正的算法决策。

假设有四座城市：

A —— B
|    |
C —— D

道路长度分别为：

道路	距离
A—B	10
A—C	2
C—D	3
D—B	1

问题：

从 A 到 B，最短距离是多少？

直接走：

$A\rightarrow B=10$

绕行：

$A\rightarrow C\rightarrow D\rightarrow B$

距离：

$2+3+1=6$

所以最短距离是6。

现在更重要的问题是：

如果你使用 BFS，按照经过的边数寻找最短路径，会得到什么？

BFS 会认为直接从 A 到 B 只经过一条边，因此它在边数意义上最短。

但实际距离却是10。

因此：

BFS 保证的是无权图中的最少边数路径，而 Dijkstra 可以在非负权图中寻找最小总权重路径。

这就是两种算法的根本区别。

尾声：两位数学家，相隔221年的共同智慧

1735年，欧拉研究柯尼斯堡的七座桥。

他没有试图找到一条不存在的路线。

而是通过研究顶点与边的关系，证明问题不可能有解。

1956年，Dijkstra 坐在阿姆斯特丹的咖啡馆里。

他没有枚举城市之间的所有路线。

而是通过一个巧妙的贪心策略，逐步确定最短距离。

他们相隔两个多世纪。

面对的问题也截然不同。

但这两个故事体现出同一种数学思想：

解决复杂问题时，最重要的突破，往往不是计算得更快，而是找到一种能够避免大量计算的表达方式。

欧拉把城市变成了图。

Dijkstra 把寻找路线变成了不断确定最小距离。

这也正是算法最迷人的地方。

本章需要真正掌握的知识

概念	核心思想
Graph	用顶点与边表示关系
Degree	与顶点关联的边的数量
Eulerian Trail	每条边恰好经过一次
DFS	使用栈或递归深入探索
BFS	使用队列逐层探索
Weighted Graph	边具有不同权重
Dijkstra	在非负权图中逐步确定最短距离
Priority Queue	优先取出权值最小或优先级最高的任务

历史资料

这一章的故事主要参考：

^{https://academic.oup.com/book/45622/chapter-abstract/394863558 · https://academic.oup.com/book/45622/chapter-abstract/394863558?utm_source=chatgpt.com}：分析欧拉的原始证明及其历史意义。
^{https://www.researchgate.net/publication/225035512_About_the_cover_Euler_and_Konigsberg%27s_Bridges_A_historical_view · https://www.researchgate.net/publication/225035512_About_the_cover_Euler_and_Konigsberg%27s_Bridges_A_historical_view?utm_source=chatgpt.com}：讨论欧拉研究七桥问题的历史背景。
^{https://www.cs.utexas.edu/EWD/transcriptions/EWD11xx/EWD1166.html · <a href="https://www.cs.utexas.edu/EWD/transcriptions/EWD11xx/EWD1166.html?utm_source=chatgpt.com" target="_blank" rel="noreferrer">https://www.cs.utexas.edu/~EWD/transcriptions/EWD11xx/EWD1166.html?utm_source=chatgpt.com}：包含1956年设计算法与咖啡馆故事。
^{https://www.cwi.nl/en/about/history/e-w-dijkstra-brilliant-colourful-and-opinionated/ · https://www.cwi.nl/en/about/history/e-w-dijkstra-brilliant-colourful-and-opinionated/?utm_source=chatgpt.com}：介绍 ARMAC 演示和 Dijkstra 的研究经历。
^{https://www.cs.cornell.edu/courses/JavaAndDS/shortestPath/shortestPath.html · https://www.cs.cornell.edu/courses/JavaAndDS/shortestPath/shortestPath.html?utm_source=chatgpt.com}：提供算法原理、正确性证明与原始论文相关材料。

下一章预告

第七章：排序算法的战争——1960年的年轻人，如何用一种简单的思想击败平方复杂度？

1959年前后。

一名年轻的英国计算机科学家来到莫斯科。

他正在参与机器翻译相关工作。

他发现，计算机查找单词时，数据的组织方式会极大影响运行效率。

如果先把单词排序，后续的查找任务可能变得简单得多。

然而，怎样才能高效地给大量单词排序？

他最初研究的方法需要大量比较。

直到有一天，他想到：

与其一次次交换相邻元素，不如先把数据分成两部分，让小的放一边，大的放另一边。

这位年轻人就是 Tony Hoare。

而他提出的算法，就是：

快速排序（Quicksort）。

下一章，我们将回到1959年的莫斯科，从 Hoare 的真实经历出发，重新审视快速排序的发明过程，并进一步探索归并排序、堆排序及它们之间的竞争。

更有意思的是：快速排序虽然平均复杂度为 $O(n\log n)$ ，却可能退化到 $O(n^2)$ 。为什么一个有着如此明显缺陷的算法，仍然成为排序史上的经典？