本课程聚焦于图算法，图是一种数据结构，用于表示一组由边连接的节点。下图展示了一个包含四个节点和四条边的图：

尽管图是数学与理论计算机科学中的抽象概念，但它们可以用来建模现实生活中的各种问题。一些典型例子包括：

• 互联网中IP数据包的路由。
• 公共交通系统中寻找最快通勤路径。
• 操作系统进程中检测死锁。

因此，图算法是每位软件开发者工具箱中强大而多用途的工具。

一点历史

图论的研究或许起源于著名的柯尼斯堡七桥问题。这是一个用图来建模现实谜题的精彩范例。

18世纪初，普鲁士城市柯尼斯堡（今加里宁格勒）由四块陆地组成，被河流隔开，并通过七座桥相互连接。数学家莱昂哈德·欧拉研究是否存在一种行走路线，能够恰好经过每座桥一次。如今，他对这一问题的分析被视为图论诞生的重要时刻之一。

欧拉将城市建模为一个图：每个城区部分用一个节点表示，每座桥用一条边表示。如下图所示：

下图中标记了一条从北柯尼斯堡出发的行走路线。该路线经过六座桥，最终到达东岛。第七座连接南城与西岛的桥已无法再被跨越。

欧拉“解决”了柯尼斯堡七桥问题，证明这样的行走路线不可能存在。他的推理是：任何遍历所有桥梁的行走路线，必须对每个城区部分做到“进入次数等于离开次数”。唯一的例外是起点和终点所在的两个区域。这意味着至少有两个中间区域必须进出次数相等。

因此，这两个中间区域所连接的桥的数量必须是偶数。然而，柯尼斯堡的四个城区每一个都连接着奇数座桥！所以，不存在一条能恰好经过每座桥一次的行走路线。

欧拉路径的算法

从图论的角度看，柯尼斯堡七桥问题本质上是在寻找一条沿着图的边行走、且每条边恰好经过一次的路径。这种路径后来被称为欧拉路径，以纪念莱昂哈德·欧拉。

欧拉指出，只有当图中恰好有两个节点连接奇数条边时，欧拉路径才可能存在。他还断言，在满足这一条件的图中，欧拉路径总是可以找到，但他并未提供证明或具体的计算算法。到了19世纪末，数学家卡尔·赫尔霍尔泽和皮埃尔-亨利·弗勒里独立发现了该命题的证明，并提出了寻找欧拉路径的具体算法。

弗勒里算法

我们首先通过弗勒里算法来学习一个图算法的实际应用。在开始之前，我们需要构造一个确实包含欧拉路径的图。我们将前面提到的柯尼斯堡图进行修改：将南柯尼斯堡与西岛之间的一座桥移动，改为直接连接北柯尼斯堡与南柯尼斯堡。

修改后的图现在仅有两个节点连接奇数条边，因此可以从南柯尼斯堡出发，到达东岛构造出一条欧拉路径。弗勒里算法描述了如何实现这一点：

1. 从一个连接奇数条边的节点开始。
2. 从当前节点选择下一条边，优先选择移除后不会使图断开的边。
3. 沿选定的边前进，并将其从图中移除。

让我们在柯尼斯堡桥图上运行该算法：

实现弗勒里算法

从概念上看，弗勒里算法相对简单。它可以用一段简短的文字描述，而且在小规模示例图上也容易手动执行。但在像 C++ 这样的编程语言中实现它，则面临诸多挑战。

迄今为止，我们对图的理解仍停留在由圆圈和线条构成的图形表示。我们的首要任务是将这种视觉化表示转化为机器可处理的形式，使用如 C++ 标准库中的 vector 等高效数据结构。

观察四节点柯尼斯堡图时，我们能一眼看出移除某条边是否会破坏图的连通性。但无论是计算机程序还是人类，当图包含数亿个节点时，都无法一次性看清整个结构。我们必须设计策略来遍历图，并判断移除某些边是否会导致图分裂成多个不连通的部分，这同样需要高效的图算法支持。

接下来的学习内容

在本课程的后续部分，你将学习：

• 图论的基本概念。
• 如何使用合适的编程数据结构在代码中表示图。
• 高效遍历图的算法。
• 如何实现优化算法，解决最短路径、网络流等问题。

本课程使用 C++ 编程语言，但代码示例也可轻松迁移到 Java 或 Python 等其他语言。完成本课程后，你将具备实现弗勒里算法等图算法的能力，用于寻找欧拉路径。