图论入门

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 图论究竟研究什么

图论研究的是一个非常小的想法：一组对象，以及一份记录哪些对象两两相连的清单。这就是这门学科的全部。它之所以值得一个半世纪的数学研究，是因为大量实际问题最终都恰恰是关于这件事的问题，而且只关于这件事。

来看四个看似毫不相关的问题。一家快递公司想找出两个仓库之间的最短路线。一个编译器需要知道构建项目各模块的顺序。一位生物学家想知道哪些蛋白质会直接或间接地相互作用。一家网络运营商想知道哪根电缆一旦被切断就会让某个地区与外界隔绝。作为故事，它们毫无共同之处。但从结构上看，它们是针对同一种对象提出的同一小组问题，解决它们的算法可以互换。正是这种可迁移性，让这门学科被早早讲授、处处使用：一旦把某个情境写成图，一大批现成的结论就立刻可用，而且没有一个结论在乎顶点原本代表什么。

注意右图中没有包含什么。城镇的位置变了，道路变直了，也没有任何信息记录某条路是另一条的两倍长。如果这些事实对你的问题很重要，就必须以边上的数字的形式把它们显式地加回来。如果不重要，那么丢掉它们恰恰是让问题变得可解的原因。

本文是一门浓缩在一页里的入门课：按顺序给出的定义，其余一切所依赖的小结论，图在真实代码中如何存储和搜索，经典问题，以及一张诚实的地图，说明哪些问题计算机几秒就能回答，哪些根本无法回答。每一节都链接到一篇更深入的文章，方便你就该主题进一步阅读。

2. 定义，以及它刻意省略的东西

几乎所有科普介绍都说图就是“用线连起来的点”。这个画面很有用，但它也正是许多人几周后卡住的原因：点和线只是这个对象的一幅图画，而不是对象本身。这个对象是一对集合。Diestel 的 Graph Theory是研究生阶段的标准参考书，它以最简洁的形式给出了定义：

图是一对集合 G = (V, E) ，满足 E ⊆ [V]²，其中 [V]² 是 V 的所有二元子集构成的集合。

展开来说，这句话讲了四件事：

• V 是一组对象，称为顶点（或节点）。对它们不做任何假设。它们可以是城市、人、原子、网页或整数。这套理论从不查看顶点的内部，它只需要能够区分两个顶点。
• E 是 V 的二元子集构成的集合。一条边字面上就是集合 {u, v}。它既不是箭头，也不是曲线，除了它连接的是哪一对顶点之外，不携带任何信息。
• 由于 E 是一个集合，一条边要么存在，要么不存在，不能出现两次。
• 由于每条边都有两个不同的元素，没有任何边会把一个顶点和它自己相连。

最后这两条推论并不是谁额外加上的规则，而是直接从集合论中推出的，满足这两条的图称为简单图。允许重复边或自环就意味着修改定义本身，第 5 节中的多重图正是这样做的。

还有两个记号随处可见。当涉及多个图时，写作 V(G) 和 E(G) 。两个衡量大小的量也各有名称：顶点的个数称为图的阶，边的条数称为图的规模，几乎所有算法书籍都将它们简写为 n = |V| 和 m = |E|.

定义中省略的东西和它包含的东西一样有启发性。这里没有几何，所以同一个图的两种画法就是同一个图，哪怕一种看起来像螺旋，另一种像网格。顶点之间没有顺序。没有距离、容量或成本；这些来自一个额外的函数，通常写作 w: E → ℝ，在问题需要时才附加上去。这个裸对象是被刻意精简的，而正是这种精简，让关于它的定理能如此广泛地适用。配套指南顶点与边对同一个定义做了更详细的阐述。

3. 起源：七座桥和一次不可能的散步

这门学科有一个明确的诞生日。1736 年，时任圣彼得堡科学院院士的莱昂哈德·欧拉提交了一篇论文，题为 Solutio problematis ad geometriam situs pertinentis，意为“关于位置几何的一个问题的解答”。问题来自普鲁士城市柯尼斯堡，也就是今天的加里宁格勒。普雷格尔河把城市分成四块陆地，由七座桥相连，市民们喜欢拿一个问题消遣：能否在城里散步，恰好经过每座桥一次？

欧拉迈出的第一步，正是本文通篇讨论的那一步。陆地的大小和形状无关紧要，桥的长度也无关紧要，唯一重要的是哪块陆地与哪块陆地相连，以及连了几次。去掉其余一切，就剩下四个对象和七个连接，现代教科书把它画成一个有四个顶点、七条边的多重图。

他的论证很短，可以完整复述。假设这样的散步存在，任取一块既不是起点也不是终点的陆地。散步每次到达那里都必须再离开，所以那块陆地上的桥是成对使用的，桥的数目必须是偶数。在柯尼斯堡，四块陆地分别有 5、3、3、3 座桥，全是奇数。一次散步只有两个端点，所以至多只能有两块陆地的桥数为奇数。四块太多了，这样的散步不存在。

欧拉还陈述了逆命题，但没有证明；这个缺口一直没有补上，直到卡尔·希尔霍尔策给出了一个构造性证明，该证明在他去世后于 1873 年发表。现代表述很清晰：一个连通图存在一条恰好经过每条边一次的闭途径，即欧拉回路，当且仅当每个顶点的度都是偶数；存在一条开的途径，即欧拉迹，当且仅当恰好有两个顶点的度是奇数。完整的故事见欧拉路径与欧拉回路指南。

接下来的一个世纪充实了这门学科的基础，从 1847 年基尔霍夫的生成树，到 1878 年西尔维斯特从化学中借用了“图”这个词，再到 1936 年柯尼希的第一本教科书。这段历史在图论的历史一文中有详细讲述。

4. 基本术语与第一个定理

本文余下部分都使用同一个贯穿始终的例子：一个有七个顶点、八条边的图。它小到可以手工验证每一个论断，又大到足以说明问题。

V = {A, B, C, D, E, F, G}                          n = 7
E = { {A,B}, {A,C}, {B,C}, {B,D}, {C,E},
      {D,E}, {D,F}, {F,G} }                        m = 8

下面是这些术语，每一个都只用这两个集合来定义：

• 相邻。由一条边连接的两个顶点。B 和 D 相邻，A 和 D 不相邻。
• 关联。一条边与它的两个端点分别关联。相邻描述的是顶点与顶点的关系，关联描述的是顶点与边的关系，初学者经常把两者搞混。
• 邻域。 N(v)，即与 v 相邻的顶点的集合。这里 N(D) = {B, E, F}。
• 度。 deg(v)，即交汇于 v 的边端点的个数，在简单图中就等于 |N(v)|。这里 deg(B) = 3 ， deg(G) = 1。
• 叶子与孤立顶点。度为 1 的顶点（如 G）和度为 0 的顶点。孤立顶点是合法的，而且当一个图由边列表构建时，它们是最常丢失的数据，因为边列表根本无法提到它们。
• 最小度与最大度。 δ(G) 和 Δ(G)，这里分别是 G 处的 1，以及 B、C、D 处的 3。

定义了度之后，第一个定理就近在咫尺了。七个顶点的度之和为 2 + 3 + 3 + 3 + 2 + 2 + 1 = 16，恰好是八条边的两倍，而这并不是这个图的巧合。

这种用两种方式计数同一集合的技巧称为双重计数，是初等组合数学的主力工具。这个引理有一个第一次见到时令人惊讶的推论：奇数度顶点的个数总是偶数。这里它们是 B、C、D 和 G，共四个。原因是算术上的：总和是偶数，偶数度顶点贡献的是偶数，所以奇数度顶点合起来也必须贡献偶数，这就要求它们的个数为偶数。用日常的话说，一个房间里与奇数个人握过手的人数一定是偶数。欧拉关于柯尼斯堡的论证，就是把这个推论应用在一次散步上。

5. 图的家族

第 2 节中的裸定义是限制最严格的一种。每个真实的建模问题最终都需要某种变体，而每种变体都是对“边可以是什么”所做的一项具体的、有名称的修改。知道自己处在哪个家族，决定了哪些算法能够适用，所以这些术语并非为学而学。

简单图是默认情形：没有自环，没有重复边，教科书中凡是不加限定的结论，说的都是它们。多重图允许平行边，伪图还允许自环。柯尼斯堡确实需要多重图，因为其中有两块陆地由两座桥相连；而一个自环会使其顶点的度增加 2，因为它的两端都连在那里。参见简单图与多重图。

有向图把无序对 {u, v} 替换为有序对 (u, v)，称为弧，因此有向图可以只包含一个方向、两个方向或都不包含，度也随之分为入度和出度。只要关系不对称，这就是正确的模型：单行道、“A 关注 B”、“模块 A 导入模块 B”、“任务 A 必须在任务 B 之前完成”。参见有向图与无向图。

带权图增加一个函数 w ，为每条边赋予一个数：公里数、分钟数、价格、容量、相似度。算法对这些数有明确的要求。Dijkstra 算法要求它们非负，Bellman-Ford 能容忍负权但不能容忍负环，而广度优先搜索完全忽略它们，所以在带权图上运行 BFS 并把结果称为最短路径，是初学者代码中最常见的错误之一。参见带权图与无权图。

二分图把顶点集分成两部分，每条边都连接这两部分。学生与课程、求职者与岗位、买家与商品：任何双边匹配的情形都是二分的。一个图是二分图，当且仅当它不包含奇环，只需一次用两种颜色给顶点着色的广度优先搜索，就能在线性时间内判定。

完全图记作 Kn，包含所有可能的边。由于一条边就是从 n 个顶点中选出 2 个，边数为 n(n-1)/2，所以 K5 有 10 条边， K100 有 4950 条边。这也是 n 个顶点的任何简单图的边数上限，图的密度正是以此为基准来衡量的。

树是没有环的连通图，是第 8 节的主题。 DAG，即有向无环图，是没有有向环的有向图，它们是一切依赖关系和一切日程安排的形态：电子表格公式、构建目标、Git 提交以及神经网络中的运算都是 DAG，而把它们排成有效顺序的算法就是拓扑排序。

还有一个家族值得记住名字：平面图可以画成没有任何边交叉的样子，这对电路布局和地图着色很重要，第 12 节还会再谈到它。

6. 途径、迹、路径与环

有四个词描述在图中的移动，日常说话时它们常被混用，但它们指的是四种不同的东西。把它们分清楚，可以在以后省去大量意想不到的困惑，因为定理是用精确的词来表述的，而它们之间的区别往往就是结论的全部内容。

• 一条途径指的是任意一个顶点序列，其中前后相继的顶点彼此相邻。没有任何禁止。一条途径可以任意多次经过同一条边、重访同一个顶点。
• 一条迹是没有重复边的途径。顶点仍然可以重复。欧拉的七桥问题要求的是一条用遍所有边的迹，所以严格地说它是欧拉迹，而不是欧拉路径。
• 一条路径是没有重复顶点的途径，这自动也禁止了重复边。当有人说“从 A 到 G 的路线”时，指的就是它。
• 一个环是一条闭路径：它在同一个顶点开始和结束，除此之外不重复任何东西。在这个例子中，B、C、E、D、B 是一个长度为 4 的环，A、B、C、A 是一个三角形，即长度为 3 的环。

以上任何一种路线的长度都是它的边数，而不是顶点数，这里正是差一错误的高发地带。距离 d(u, v) 是最短路径的长度。这里 d(A, G) = 4，沿 A、B、D、F、G；路线 A、C、E、D、F、G 也能到达，但用了五条边，所以它是一条路径，但不是最短路径。直径是任意两个顶点之间的最大距离，是描述一个网络有多分散的简洁方式。

有一个事实可以立即推出，而且会被反复用到：如果存在从 u 到 v 的途径，就存在从 u 到 v 的路径。把两次访问同一顶点之间的那段回路剪掉，就得到一条更短的途径，因此这种“手术”最终会得到一条没有重复顶点的途径。这就是可达性算法从不考虑途径的原因。

7. 连通性、连通分量与不能失去的边

如果每个顶点都能从其他任何顶点到达，这个图就是连通的。否则，它会分裂成若干连通分量，即内部连通的极大部分。对于任何不是你亲手构建的图，连通性都是第一个值得检查的东西，因为数量惊人的真实数据集是分成好几块到来的，而大多数“算法返回了无穷大”之类的错误报告，其实都是用惨痛的方式发现了这个事实。

在一个连通图中，结构的某些部分比其他部分更关键。桥是这样一条边：删除它会使连通分量的个数增加；而割点（又称关节点）是删除后同样会产生这种效果的顶点。它们是单点故障所在，找出它们是任何重视可靠性的网络的标准初步分析。

在这个例子中，边 DF 和 FG 是桥，D 和 F 是割点。注意哪些边不是桥：位于环上的五条边都不是，因为环总能提供一条绕行的路。这就是一般规律，值得作为一个事实而不仅是一个观察来陈述。一条边是桥，当且仅当它不在任何环上。同样的直觉也解释了为什么真实网络的冗余是用环来衡量的：第二条路线就是一个经过第一条路线的环。

对于有向图，这个概念一分为二：如果忽略弧的方向后得到一个连通图，有向图就是弱连通的；如果每个顶点都能沿着弧的正确方向到达其他所有顶点，它就是强连通的。Tarjan 于 1972 年提出的算法可以在线性时间内找出强连通分量，而在依赖图中，一个包含不止一个顶点的强连通分量恰好就是一个循环依赖。

从计算的角度看，这一切都很廉价。一次广度优先或深度优先扫描就能在 O(n + m)时间内标记出每个连通分量，而桥和割点可以通过一次加上 Tarjan low-link 值的深度优先搜索得到，同样是 O(n + m)。在做任何其他事情之前，几乎没有理由不先检查连通性。

8. 树：最有用的特例

一棵树是没有环的连通图。它无疑是这门学科中最重要的特例，一方面因为树在计算机科学中无处不在，另一方面因为当输入恰好是一棵树时，大量困难的问题都会变得容易。

树的非凡之处在于，许多听起来各不相同的描述指向的是同一类对象。对于有 n 个顶点的图 G，下列说法全都等价，其中任何一条都可以作为定义：

1. G 连通且没有环。
2. G 连通且恰好有 n - 1 条边。
3. G 没有环且恰好有 n - 1 条边。
4. 任意两个顶点之间恰好有一条路径。
5. G 连通，且删除任意一条边都会使它不连通，因此每条边都是桥。
6. G 没有环，且添加任意一条新边都会恰好产生一个环。

这些等价性通过一个循环蕴含链来证明，详见图论中的树指南。有两个推论值得随时记在心里。边数是被确定的，所以一棵有 100 个顶点、120 条边的“树”不是树，说明上游某处出了错。而路径的唯一性正是树问题容易的原因：没有什么需要搜索，因为永远只有一条路线。

一片森林是不一定连通的无环图，即若干棵树的不交并；一个有 n 个顶点、c 个连通分量的森林恰好有 n - c 条边。连通图的生成树是一个包含所有顶点、且本身是树的子图，是让图保持为一个整体的最经济的骨架。两种遍历都会顺带免费生成一棵，而当边带有权重时，寻找权重最小的那一棵就是最小生成树问题。

树还有有根的版本：选定一个顶点作为根，于是父节点、子节点、祖先、子树和深度这些词就有了意义，例如文件系统、语法树和堆。选择根是叠加在图之上的一个决定，而不是图本身的性质，这正是关于有根树的那篇文章的要点。

9. 图在计算机中如何存储

到目前为止讲的都是数学。一旦机器必须回答关于图的问题，你就得选择它在内存中的布局，而这个选择并不是实现细节：它会让不同操作的开销相差上千倍，而表示方式选得不合适，是正确的算法跑得太慢最常见的原因。标准布局有三种，它们存储的信息完全相同。

所谓边列表，就是把集合 E 原样写出来。它很紧凑，是 CSV 文件或 API 交给你的格式，也是 Kruskal 算法想要的格式，因为这个算法按权重对边排序，从不查询某个特定顶点。它的弱点是，“D 的邻居有哪些？”这个问题意味着要扫描全部 m 行。

而邻接矩阵则是一个 n 乘 n 的网格，当边存在时单元格 (u, v) 为 1。判断两个给定顶点是否相邻只需一次查找；对于无向图，矩阵是对称的，所以每个事实都存了两遍。代价是空间：无论有没有边，都要 n 的平方个单元格。它也是通往谱方法的大门，在谱方法中，矩阵或与之密切相关的拉普拉斯矩阵的特征值能揭示聚类和连通性，这是机器学习中的谱图论的主题。

至于邻接表，它为每个顶点保存其邻居的列表。遍历 v 的所有邻居需要 O(deg v)，这是最优的，总空间为 O(n + m)。这是实践中的默认选择，也是下文所有遍历所假定的布局。

在实践中起决定作用的是，真实网络都是稀疏的：无论网络变得多大，平均邻居数都维持在几十以内，因为路口只有三四条路，人的朋友数量也是有限的。对于一个有一百万个顶点和五百万条边的图，邻接表大约保存一千万个条目，而矩阵需要一万亿个单元格，也就是好几 TB，而这个图原本可以轻松装进内存。当图很小、确实稠密或要用于线性代数时，使用矩阵；否则使用邻接表。更深入的讨论，包括压缩稀疏行（CSR）布局，见图的表示。

从边列表构建邻接表只需四行代码，而中间那行注释正是初学者容易出错的地方：

edges = [('A','B'), ('A','C'), ('B','C'), ('B','D'),
         ('C','E'), ('D','E'), ('D','F'), ('F','G')]

graph = {v: [] for v in 'ABCDEFG'}   # 从顶点集 V 出发，这样孤立顶点才能保留下来
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)               # 有向图请删去这一行

从顶点集而不是从边出发，才能让孤立顶点留在图中。如果顺手从边列表中逐步构建字典，任何没有边的顶点都会悄无声息地消失，n 随之改变，所有以 n 为除数的计算都会出错。

10. 遍历：广度优先与深度优先

几乎每个图算法都是附带一些记录工作的遍历。遍历有两种，它们只差一种数据结构，而理解这个区别，是初学者在这门学科上所能投入的最有价值的一小时。两者都从一个顶点出发，维护一组已发现但尚未处理的顶点，然后重复：取出一个，查看它的邻居，把新发现的加入。广度优先搜索按照顶点进入的顺序把它们取出，使用的是队列。深度优先搜索取出最近加入的那个，使用的是栈或递归函数的调用栈。这一个选择，造就了两种截然不同的探索形态。

下面是完整的广度优先搜索，它返回访问顺序、到起点的距离，以及可用来重建实际路线的父节点树：

from collections import deque

def bfs(graph, start):
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()          # 队列：先进先出
        order.append(u)
        for v in graph[u]:
            if v not in dist:        # 尚未发现
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return order, dist, parent

order, dist, parent = bfs(graph, 'A')
# order  ['A', 'B', 'C', 'D', 'E', 'F', 'G']
# dist   {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3, 'G': 4}

关键性质就在字典 dist 里。由于 BFS 会先处理完一整层再开始下一层，它第一次到达某个顶点时所用的边数就是最少的，所以 BFS 能解决无权图上的最短路径问题，时间为 O(n + m)。在所有边代价相同时还去用 Dijkstra，纯属白费功夫。

深度优先搜索是同一副骨架，只是把队列换成了栈：

def dfs(graph, start):
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()              # 栈：后进先出
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(graph[u]): # 逆序压栈，使第一个邻居最先被取出
            if v not in seen:
                stack.append(v)
    return order

dfs(graph, 'A')   # ['A', 'B', 'C', 'E', 'D', 'F', 'G']

DFS 不给出距离，真正有用的输出是它完成各顶点的顺序，而不是开始访问它们的顺序。拓扑排序、环检测、强连通分量和寻找桥，都建立在这个完成顺序之上，这源于 Tarjan 1972 年的论文，正是它把深度优先搜索从一种技巧变成了一整套工具。

关于两者更完整的比较，包括各自容易引发的错误，见 BFS 与 DFS 对比。

11. 经典问题及其算法

掌握了遍历，标准问题目录就触手可及了。其中每一个都是人们在真实网络上确实会问的问题，每一个都有一个以名字命名的算法。

最短路径。无权时，BFS 就能解决。权重非负时， Dijkstra 算法（1959 年发表于一篇仅三页的短文）按距离递增的顺序确定各顶点，配合良好的优先队列，运行时间为 O(m + n log n) 。存在负权时，Dijkstra 的核心假设失效，你需要 Bellman-Ford，它把每条边松弛 n-1 次，用时 O(nm) ，还能顺带检测负环。要一次求出所有顶点对， Floyd-Warshall 用三重循环在 O(n3) 时间内完成；而当你有一个目标，并对剩余距离有合理的估计时， A* 搜索会利用这个估计，只考察图的一小部分。完整的决策树见最短路径算法。

最小生成树。找出让带权图保持连通的最便宜边集。Kruskal 算法对边排序，只要不构成环就加入，并借助并查集（union-find）结构在近乎常数时间内完成判断；Prim 算法则让一棵树向外生长，每次都选取离开这棵树的最便宜的边。两者都是贪心算法，都可证明是最优的，运行时间都是 O(m log n)。铺设电缆和光纤的最低成本方案背后就是这个算法，它也出现在聚类方法中。

排序与流。给定一个依赖关系的 DAG，拓扑排序会给出一个每项任务都排在其所依赖任务之后的顺序，用时 O(n + m)，并且恰好在存在环时失败。给定一组带容量的管道，最大流问题问的是从源点到汇点最多能输送多少；它由 Ford 和 Fulkerson 于 1956 年形式化，可以对交通、带宽、供应链建模，并通过一个标准归约处理二分匹配。参见网络流、最大流与最小割。

着色。给顶点贴上标签，使任意两个相邻顶点的标签都不相同，并且所用标签尽可能少。这个最少数目称为色数，它可以为考试排期、频率分配和寄存器分配建模。与上面所有问题不同，这个问题是 NP 难的，实践中依赖启发式方法。参见图着色问题。

回路。哈密顿环恰好访问每个顶点一次，而旅行商问题要求找出最便宜的那一个。它看起来只是欧拉 1736 年问题的一个小变体，后者可在线性时间内求解，然而它却是整个目录中最难的问题之一。它在实践中的近亲，即在容量限制下从一个仓库出发为车队规划路线，就是车辆路径问题。

12. 五个值得记住名字的结论

一门入门课，一半是一组算法，一半是一组塑造你思考这些对象方式的结论。第 4 节的握手引理是其中第一个。下面这五个同样经常出现，在面试中、论文里和日常交流中都是如此，而且每一个都能用一句话说清楚。

欧拉的遍历所有边判据（1736 年，1873 年由希尔霍尔策补全）

一个连通图存在一条恰好经过每条边一次的闭迹，当且仅当每个顶点的度都是偶数；存在一条开迹，当且仅当恰好有两个顶点的度是奇数。这是最有价值的那类定理：它把在一个巨大的路线空间中的搜索，变成了一个通过计数就能完成的线性时间检查。

欧拉的平面图公式（1758 年）

画出一个没有交叉的连通平面图，令 f 为面的个数，包括无界的外部区域。那么

n - m + f = 2

按图中方式画出的这个贯穿全文的例子有 n = 7、m = 8，以及三个面：三角形 ABC、四边形 BCED 和外部区域，而确实 7 - 8 + 3 = 2。这个推论相当有力：任何至少有三个顶点的简单平面图都满足 m ≤ 3n - 6，所以平面图总是稀疏的，而 K5 有 5 个顶点和 10 条边，不可能是平面图，因为 3n - 6 等于 9。1930 年的库拉托夫斯基定理补全了这幅图景：一个图是平面图，当且仅当它不包含 K5 或 K3,3的细分。Hopcroft 和 Tarjan 于 1974 年证明了平面性可以在线性时间内检验。

四色定理（Appel 与 Haken，1976 年）

每个平面图都可以用至多四种颜色正确着色，所以任何地图都不需要超过四种颜色，就能让有共同边界的国家颜色不同。弗朗西斯·格斯里于 1852 年提出这个问题，它抵抗了 124 年的证明尝试。最终的论证把问题归结为有限个构形，再用计算机逐一检查，这引发了一场关于什么才算证明的真正的哲学争论；1997 年，Robertson、Sanders、Seymour 和 Thomas 简化了这一证明，2005 年 Georges Gonthier 在 Coq 中完成了形式化验证。注意其中的不对称：四种颜色总是够用，但判定三种颜色是否够用却是 NP 完全的。

柯尼希定理（1931 年）

在二分图中，最大匹配的大小等于最小顶点覆盖的大小。匹配是一组没有公共端点的边，是把人分配到岗位的一种方式；顶点覆盖是一组触及每条边的顶点。两个看似无关的优化问题有相同的答案，这是大多数学生遇到的第一个对偶性，也正是它使最大匹配可以在多项式时间内计算。在一般图中，这个等式不成立，最小顶点覆盖是 NP 难的。

最大流最小割定理（Ford 与 Fulkerson，1956 年）

在任何流网络中，从源点到汇点的最大流等于分隔它们的最小割的总容量：你最多能推过去的量，恰好就是最紧的瓶颈所允许的量。这又是对偶性，而且是它最常被引用的形式，把对所有流的最大化转化为对所有割的最小化。它是图像分割、项目选择和可靠性分析的基础，而柯尼希定理可以作为它的一个特例推出。

13. 什么容易、什么困难，以及为什么这很重要

初学者在图论上能学到的最有实际价值的东西，并不是某个算法，而是这样一个事实：两个问题可以用几乎相同的话来表述，却分处一道巨大计算鸿沟的两侧。在一个有数百万顶点的图上，找两个顶点之间的最短路径只需几毫秒；而找同样两个顶点之间的最长简单路径却是 NP 难的，超过几十个顶点就毫无希望。判断一个图是否存在一条把每条边都恰好经过一次的闭迹，只需一次线性时间的度数检查；判断它是否存在一个把每个顶点都恰好经过一次的环，则是 NP 完全的。判断两种颜色是否够用只需一次 BFS；判断三种颜色是否够用却是 NP 完全的。

正式的说法是，一大类图论问题是 NP 完全的，这个概念由 Cook 于 1971 年提出，Richard Karp 在 1972 年给出了第一份有分量的目录，他著名的 21 个问题清单以图论问题为主：团、顶点覆盖、哈密顿回路、色数、反馈弧集等等。这些问题中没有任何一个已知有多项式时间算法，而只要其中任何一个有，所有问题就都有。没有人认为这会发生。

实际的后果不是绝望，而是换一个问题来问。当一个问题落在右边那一栏时，你就不再追求最优解，而是在四种诚实的策略之间做选择：

• 接受近似解。对于度量 TSP，Christofides 1976 年的算法能在多项式时间内保证得到一条长度至多为最优解 1.5 倍的回路。
• 使用启发式方法并加以衡量。 2-opt 或模拟退火等局部搜索方法，在数千座城市的实例上经常能达到距最优仅百分之一二的结果，但没有任何保证。
• 利用你的实例的结构。一般情况下困难，并不意味着对你来说困难：弦图上的着色很容易，许多问题在树上和树宽较小的图上都很容易，而道路网络具有专门的路径规划算法可以尽情利用的几何结构。
• 精确求解较小的实例。整数规划求解器经常能为包含数千座城市的 TSP 实例证明最优性。指数级并不意味着不可能，而是意味着上限会很快到来。

需要提醒一句：“NP 难”描述的是输入规模增长时的最坏情况，而不是对你手头具体问题的判决。关于每个算法开销的更完整讨论，见图算法与复杂度。

14. 图究竟出现在哪里

说图论无处不在很容易，但值得拿出证据。下面就是本文的内容此刻正在发挥作用的地方，就在你阅读这篇文章所用的设备上。

导航。每个路线规划应用都把道路网络建模为带权有向图：路口是顶点，路段是以预计行驶时间为权重的弧。查询的是最短路径，而算法是 Dijkstra 和 A* 经过精心工程优化的后代，它利用预先计算好的层次结构，使一条横跨大陆的路线只涉及几千个顶点，而不是数千万个。单行道是图必须有向的原因，实时路况是权重每分钟都在变化的原因。

搜索与社交平台。万维网是由网页和链接构成的有向图，而 Brin 和 Page 于 1998 年描述的 PageRank，根据一个随机点击链接的浏览者最终停留在某个网页上的概率来为网页排名，这实际上是在邻接结构上计算特征向量。在社交平台上，人是顶点，关系是边：米尔格拉姆 1967 年的信件实验催生了广为流传的“六度分隔”，而 2012 年对整个 Facebook 社交图的一项分析得出，两个用户之间的平均距离为 4.74。社群发现、好友推荐和影响力估计，都是大规模运行的标准图计算。

软件工程。构建系统、包管理器和电子表格引擎都维护着一个 DAG 并对它进行拓扑排序。版本控制历史是一个由提交构成的 DAG，而合并就是一个关于公共祖先的问题。编译器为优化构建控制流图，为寄存器分配构建冲突图，其中分配寄存器就是字面意义上的图着色，而死代码消除则是一个可达性查询。参见软件工程中的图论。

物流。配送路线规划就是车辆路径问题，仓库选址就是设施选址问题，而供应链则是带容量的流网络。在这里，好算法和差算法之间的差距是用燃油和工资来衡量的，研究这些问题的领域就是运筹学。

科学与机器学习。分子是由原子和化学键构成的图，检索化学数据库就是子图同构问题。基因组组装通过在 de Bruijn 图中寻找欧拉路径来重建序列，让欧拉 1736 年的判据在 280 年后依然大显身手。谱聚类利用图拉普拉斯矩阵的特征向量对数据进行划分，而图神经网络通过沿边传递消息，把卷积推广到不规则结构上。电网和电信网络要分析其中的桥和割点，因为连锁故障正是从那里开始的。更全面的综述见图论的应用。

15. 初学者必犯的错误

下面这些错误会在学生代码、面试和生产环境的缺陷中一再出现。每一个只要被点名见过一次，就很容易避免。

• 丢失孤立顶点。从边列表构建图，意味着任何没有边的顶点永远不会出现。阶 n 悄无声息地改变，平均值算错，连通分量的计数也会偏少。请先构建顶点集。
• BFS 中标记已访问太晚。应当在顶点入队时就标记它，而不是在出队时。出队时才标记，会让同一个顶点每经由一条关联边就入队一次，把一个线性算法变成一个内存问题。
• 在带权图上运行 BFS。 BFS 最小化的是边的条数，而不是边的总权重。在一个两条边的路线代价为 100、五条边的路线代价为 5 的图上，BFS 会信心十足地返回昂贵的那条。带权图需要 Dijkstra。
• 在有负权的图上运行 Dijkstra。 Dijkstra 假设一个顶点一旦确定，以后就不会再出现通往它的更便宜的路线。一条负权边就会打破这个假设，而输出会悄无声息地出错，而不是报错。请使用 Bellman-Ford。
• 按顶点数计算路径长度。长度是边的条数，所以经过五个顶点的路径长度是 4。最短路径代码中相当一部分差一错误都源于此。
• 忽视图属于哪个家族。一个在无向图上正确的算法，可能在有向图上悄无声息地出错；一个针对简单图证明的结论，可能在多重图上不成立。在选用算法之前先确认图的家族。
• 假定图是连通的。真实数据是分成若干块到来的。在相信任何距离、直径或平均值之前，先检查连通分量的个数。
• DFS 递归过深。在一条有一百万个顶点的路径上运行递归 DFS，需要一百万个栈帧。当输入可能很大时，请写迭代版本。
• 在无向图中只添加一个方向。一条无向边必须同时出现在两个邻接表中。漏掉第二个 append，得到的图在画出来时看似正确，但在每一次遍历中表现得都像一个有向图。
• 轻信画出来的图。图画中两条边交叉毫无意义。只有集合才重要，这就是为什么“这个图是平面图吗？”是一个真正的问题，而不是眯着眼看看图就能解决的事情。
• 以为 n - 1 条边就意味着树。只有同时满足连通或无环时才成立。一个三角形加上一个孤立顶点，有 4 个顶点和 3 条边，却不是树。

16. 下一步学什么

有用的下一步是亲手构建一个图并在上面运行点什么，而不是继续阅读更多定义。把这个贯穿全文的例子输入交互式可视化工具，从 A 开始运行广度优先搜索，看着各层依次填满；再从同一个顶点运行深度优先搜索，比较两者的顺序。九十秒的动手操作，胜过再多的文字。

之后，自然的学习顺序就是本文的顺序：术语、遍历、带权最短路径、生成树，然后是更难的问题。图论学习路线图给出了这条路线和时间安排，结构化课程则以交互方式带你走完它。准备技术面试的话，图论编程面试指南涵盖了真正会出现的题型，另可参考算法速查表。

教科书方面：West 的 Introduction to Graph Theory 是本科标准课程的成书版本，Diestel 的 Graph Theory 是研究生阶段的参考书，也是第 2 节定义的出处，而 Cormen、Leiserson、Rivest 和 Stein 书中的图论章节，至今仍是讲解实现最清晰的资料。包括课程和视频系列在内的更完整比较，见学习图论的最佳资源。

17. 术语表

上文用到的所有术语，集中在一处。

19. 参考文献

上文的定义、定理、年份和复杂度界均出自以下文献，按时间顺序排列。

1. Euler, L. (1736). "Solutio problematis ad geometriam situs pertinentis." Commentarii Academiae Scientiarum Petropolitanae 8（1741 年出版），128 至 140 页。关于柯尼斯堡七桥的论文。
2. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4，109 至 140 页。n - m + f = 2 背后的多面体公式。
3. Kirchhoff, G. (1847). "Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird." Annalen der Physik 148(12)，497 至 508 页。
4. Hierholzer, C. (1873). "Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren." Mathematische Annalen 6(1)，30 至 32 页。
5. Sylvester, J. J. (1878). "Chemistry and Algebra." Nature 17，284 页。“graph”一词在现代意义上的首次使用。
6. Cayley, A. (1889). "A theorem on trees." Quarterly Journal of Pure and Applied Mathematics 23，376 至 378 页。
7. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15，271 至 283 页。
8. König, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38，116 至 119 页。
9. König, D. (1936). Theorie der endlichen und unendlichen Graphen. Leipzig: Akademische Verlagsgesellschaft.
10. Ford, L. R. and Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8，399 至 404 页。
11. Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society 7(1)，48 至 50 页。
12. Prim, R. C. (1957). "Shortest connection networks and some generalizations." Bell System Technical Journal 36(6)，1389 至 1401 页。
13. Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik 1，269 至 271 页。
14. Floyd, R. W. (1962). "Algorithm 97: Shortest path." Communications of the ACM 5(6)，345 页。
15. Held, M. and Karp, R. M. (1962). "A dynamic programming approach to sequencing problems." Journal of the Society for Industrial and Applied Mathematics 10(1)，196 至 210 页。
16. Milgram, S. (1967). "The small world problem." Psychology Today 2(1)，60 至 67 页。
17. Cook, S. A. (1971). "The complexity of theorem-proving procedures." Proceedings of the Third Annual ACM Symposium on Theory of Computing，151 至 158 页。
18. Karp, R. M. (1972). "Reducibility among combinatorial problems." 载于 Complexity of Computer Computations，85 至 103 页。纽约：Plenum Press。
19. Tarjan, R. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2)，146 至 160 页。
20. Hopcroft, J. and Tarjan, R. (1974). "Efficient planarity testing." Journal of the ACM 21(4)，549 至 568 页。
21. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. 报告 388，卡内基梅隆大学。
22. Appel, K. and Haken, W. (1977). "Every planar map is four colorable." Illinois Journal of Mathematics 21(3)。第一部分，429 至 490 页；第二部分（与 J. Koch 合著），491 至 567 页。
23. Fredman, M. L. and Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM 34(3)，596 至 615 页。
24. Brin, S. and Page, L. (1998). "The anatomy of a large-scale hypertextual Web search engine." Computer Networks and ISDN Systems 30(1 至 7)，107 至 117 页。
25. West, D. B. (2001). Introduction to Graph Theory，第 2 版。Upper Saddle River：Prentice Hall。
26. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244. London: Springer.
27. Gonthier, G. (2008). "Formal proof: the four-color theorem." Notices of the American Mathematical Society 55(11)，1382 至 1393 页。
28. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). 算法导论 (Introduction to Algorithms)，第 3 版。马萨诸塞州剑桥：MIT Press。
29. Backstrom, L., Boldi, P., Rosa, M., Ugander, J. and Vigna, S. (2012). "Four degrees of separation." Proceedings of the 4th Annual ACM Web Science Conference，33 至 42 页。
30. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。第 2 节所引定义的出处。