有向图与无向图详解

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 两种定义并列对照

有向图与无向图的区别在于定义中的一个词：连接两个顶点的对是否有序。本文的其余内容，包括哪些算法依然有效，都是这个词的推论。

所谓无向图，就是顶点与边指南中介绍的标准对象。按照 Diestel 的 Graph Theory：

G = (V, E)      其中   E ⊆ [V]²      边是无序对 {u, v}

而有向图（英文 digraph）则把无序对换成有序对：

D = (V, A)      其中   A ⊆ V × V      弧是有序对 (u, v)

由于 (u, v) 和 (v, u) 是不同的有序对，二者可以同时存在；同时包含二者的有向图就有一个双向弧对，位于 u 和 v之间。在无向世界里没有什么需要区分： {u, v} 和 {v, u} 是同一个集合，所以这条边要么存在一次，要么根本不存在。

Diestel 还给出了一种更一般的表述，值得了解，因为它经得起真实数据的考验。有向图是一个由两个不相交集合构成的对 (V, E) ，并带有两个映射

init: E → V        为每条边指定其起点
ter:  E → V        为每条边指定其终点

这里的弧本身就是对象而不是一个对，因此该定义无需任何特殊处理就能容纳平行弧和自环。它是多重图所需的关联函数定义在有向情形下的对应物，也正因如此，一份每天有三班从 A 飞往 B 的独立航班的时刻表，依然是一个完全合格的有向图。

它与逻辑的形式联系是精确的，值得说明一次：没有自环的无向图恰好是一个反自反的对称关系，定义在 V上；而有向图是定义在 V上的任意二元关系。方向，就是当你不再要求关系对称时所得到的东西。

这两个图是全文的贯穿示例。有向图为

V = {A, B, C, D, E}
A = { (A,B), (B,C), (C,A), (C,D), (D,E), (E,D) }        6 条弧

左边的无向图是它的基础图，有 5 条边，因为 D 与 E 之间方向相反的两条弧合并成了一条边 {D, E}。

2. 边、弧、弧尾与弧头

定义变了，术语也随之改变，而且这些改变并非装饰。Bang-Jensen 和 Gutin 的 Digraphs是有向图方面的标准参考书，它刻意为不同对象保留不同的词，使任何命题都不会对所指对象产生歧义。

有两个术语经常被混淆，值得单独说明。定向图是没有双向弧对的有向图：你取一个无向图，为每条边选定一个方向。每个定向图都是有向图，但同时包含 (u,v) 和 (v,u) 的有向图不是定向图。这一区别正是第 5 节的全部主题。

3. 度一分为二

在无向图中，一个顶点的度统计与它相接的边端数，握手引理说这些计数之和等于边数的两倍。在有向图中，每条弧只有一个弧尾和一个弧头，而不是两个对称的端点，所以一个计数分成了两个：

• 出度 d+(v)：弧尾为 v的弧的数量。
• 入度 d-(v)：弧头为 v的弧的数量。

而那个恒等式也一分为二：

无向     ∑v∈V deg(v)   =  2m           每条边有两个端点

有向     ∑v∈V d+(v)  =  ∑v∈V d-(v)  =  |A|
                                             每条弧有一个弧尾和一个弧头

少了的因子 2 常常让人困惑。这并不是另一个定理，而是同一个双重计数论证，只是作用在一个集合上，其元素现在分别计入两个独立的和，而不是在一个和中计两次。

在贯穿示例上验证一下。出度为 A 1、B 1、C 2、D 1、E 1，总和为 6。入度为 A 1、B 1、C 1、D 2、E 1，总和也是 6，正是弧的数量。在基础无向图上，度为 2、2、3、2、1，总和为 10，是其 5 条边的两倍。

由此立即得到两类有名字的顶点，它们在无向图中完全没有对应：

• 所谓源点，是入度为 0 的顶点：没有弧指向它。
• 所谓汇点，是出度为 0 的顶点：它不指向任何顶点。

源点和汇点是流网络的入口和出口，也是拓扑序的起点和终点。在无向图中，这些概念根本无法表达。

4. 矩阵与邻接表中的变化

方向在存储中和在定义中一样明显，其差异正如 Cormen、Leiserson、Rivest 和 Stein 在 Introduction to Algorithms中所阐述的。

邻接矩阵。无向图的矩阵总是对称的， A = AT，因为 {u, v} 和 {v, u} 是同一条边。有向图的矩阵一般不对称，而这种不对称承载着真实的信息：

• 行和是出度，列和是入度。在无向情形下两者都给出度，所以这一区别从未出现。
• 转置 AT 恰好是反向图，即每条弧都被翻转。翻转无向图不起任何作用，这正是以下事实的另一种说法： A = AT。
• 元素 (Ak)uv 统计长度为 k 、从 u 到 v 的途径数，两种情形都是如此；但在有向情形下这些途径必须遵循箭头，所以这个数一般不同于 (Ak)vu。

邻接表。无向图把每条边存储两次，每个端点的表中各存一次，因此表中共有 2m 个条目。有向图把每条弧只存储一次，存在弧尾的表中，共 m 个条目。这带来一个第一次遇到时令人意外的实际后果：要沿反方向遍历有向图，你需要第二个结构，即反向邻接表，因为一个顶点的表只告诉你能去哪里，而不是你从哪里来。Kosaraju 求强连通分量的算法正是基于这一观察，在第二遍中遍历反向图。

由此得到两个上界。有 n 个顶点的简单无向图最多有 n(n-1)/2 条边。没有自环的有向图最多有 n(n-1) 条弧，恰好是两倍，因为每个有序对现在都是一个独立的位置。

5. 定向与基础图

两个世界由一对方向相反的构造联系起来，给它们正确命名能消除很多混乱。

• 给定有向图 D，它的基础图就是忘掉箭头后得到的图：把每条弧 (u, v) 换成边 {u, v} ，并去掉重复。贯穿示例的基础图有 5 条边，比有向图的 6 条弧少一条，因为 D 与 E 之间的双向弧对合并了。
• 给定无向图 G，它的一个定向是为每条边恰好选定一个方向所得到的有向图。结果是一个定向图：没有双向弧对，因为每条边只产生一条弧。

这两个操作并不互逆。取基础图会丢失任何定向都无法恢复的信息，而且有 m 条边的图有 2m 种不同的定向，因为每条边都是一个独立的二元选择。贯穿示例的基础图有 5 条边，因此有 32 种定向，而原来的有向图甚至不在其中，因为它含有双向弧对。

这就引出了下一节要回答的问题。在这 2m 种定向中，是否有某一种是好的，也就是说仍然可以到达任何地方？

6. Robbins 定理：哪些街道可以改为单行道

1939 年，Herbert Robbins 在 American Mathematical Monthly 上发表了一篇短文，标题令人难忘：“A theorem on graphs, with an application to a problem of traffic control”。问题正是城市规划者所面对的：如果每条街道都改成单行道，司机还能到达城市的每个角落吗？

Robbins 定理。连通的无向图存在强连通定向，当且仅当它没有桥。

所谓桥，又称割边，是删除后会使图不连通的边。没有桥的连通图恰好是 2-边连通图，即每条边都位于某个环上的图。（这里连通性很重要：不连通的图可以没有桥，却不是 2-边连通的。）

证明的一个方向比较容易，值得一看，因为它解释了整个结论。假设 e = {u, v} 是一座桥，删除它会把图分成包含 u 的分量和包含 v的分量。任何定向都必须让 e 朝某一个方向。如果它变成 (u, v) ，那么 v一侧的任何顶点都无法回到 u一侧，因为 e 是唯一的连接，而它现在指向了错误的方向。如果它变成 (v, u) ，同样的论证反过来成立。无论哪种情况，定向都不是强连通的。反方向的结论，即每个无桥连通图确实存在强连通定向，才是实质性的一半；标准证明运行一次深度优先搜索，把树边定向为背离根的方向，把回边定向为指向根的方向。

贯穿示例让这个定理变得具体。它的基础图含有三角形 A、B、C，这部分没有桥，但边 {C, D} 和 {D, E} 都是桥。所以根据 Robbins 定理，这个图没有任何定向是强连通的，这也正是图中的有向图无论怎样重画箭头都不是强连通的原因。

Nash-Williams 在 1960 年推广了这一结果：每个 2k-边连通的无向图都有一个 k-弧连通的定向，Robbins 定理就是 k = 1的情形。实际含义不变：单行道系统只在路网有冗余的地方才是安全的，而连接郊区与城区其余部分的唯一一条道路，永远不能改成单行道，否则就会把郊区隔绝。

7. 连通性变成三个不同的问题

在无向图中，连通性只是一个是或否的问题：每对顶点之间是否都有路径？方向把它变成了一个层级。这一分类出自 Harary、Norman 和 Cartwright 的 Structural Models，它是有向图理论中最常被跳过、也最常被用到的部分。

每个条件都蕴含它下面的条件，所以强连通蕴含单向连通，单向连通蕴含弱连通。贯穿示例恰好处在层级的中间，这也是实践中的常见情况：你可以从三角形 A、B、C 出发到达 D 和 E，却永远回不来。

有用的细化是不再询问整个有向图，而是询问它的各个部分。强连通分量（SCC）是一个极大的顶点集合，其中每个顶点都能到达其他所有顶点。每个有向图都能唯一地划分为若干 SCC，把每个 SCC 收缩成一个顶点，就得到缩点图，它总是无环的。最后这一点并非偶然：如果缩点图中有环，环上的每个分量都能到达其他所有分量，那么它们从一开始就应该是同一个 SCC。

求 SCC 只需线性时间。Tarjan 1972 年的论文“Depth-first search and linear graph algorithms”利用 low-link 值，在一次深度优先遍历中完成；Kosaraju-Sharir 方法则用两遍，第二遍在反向图上进行。两者的运行时间都是 O(n + m)，而且都没有无向的对应物，因为在无向图中，任何一次遍历都能直接得到连通分量。

8. 环、DAG 与拓扑序

一旦涉及箭头，“环”这个词就悄悄变得更严格，这一差别会引发真正的 bug。

在简单无向图中，环是没有重复顶点的闭途径，至少需要三个顶点，因为沿一条边走过去再直接走回来不算环。没有环的无向图称为森林，连通的森林称为树。

在有向图中，有向环必须一路沿着箭头走完，而且双向弧对也算：两条弧 (D, E) 和 (E, D) 构成一个长度为 2 的有向环。没有有向环的有向图称为 DAG，即有向无环图，而 DAG 具有无向世界中任何东西都没有的性质：

有向图存在拓扑序（顶点的一种线性排列，使每条弧都指向前方），当且仅当它是无环的。

Kahn 1962 年发表在 Communications of the ACM 上的论文给出了标准算法：反复取一个入度为 0 的顶点，输出它，并把它连同其出弧一起删除。如果有向图被删空，输出就是一个拓扑序；如果还剩顶点却无法继续，那么每个剩余顶点都位于某个环上。详细内容见拓扑排序指南。

由此引出两个陷阱：

• 基础图有环，说明不了任何问题。贯穿示例的基础图含有三角形 A、B、C，其有向图在那里也确实含有有向环。但如果把同一个三角形定向为 A → B、 A → C、 B → C ，就得到一个 DAG，而它的基础图仍然有环。无向环检测无法回答有向问题。
• 环检测是另一个算法。在无向图中，DFS 只要遇到一个不是来源父节点的已访问顶点，就找到了环。在有向图中这个检验是错误的：你必须找到一条指向仍在当前递归栈上的顶点的回边，因为指向已完成顶点的弧是无害的。

9. 哪些算法可以沿用，哪些会失效

实际问题是：无向工具箱中哪些部分能够迁移过来。规律比乍看之下更清楚：凡是只沿边正向前进的都能迁移，凡是依赖对称性的都不行。

最小生成树这一行连有经验的人都会栽跟头。Kruskal 和 Prim 算法是在对称成本结构上的贪心算法，两者都经受不住定向。正确的有向问题是最小生成树形图：选择总权重最小的弧集，使每个顶点都能从一个固定的根到达。Chu 和 Liu 于 1965 年、Edmonds 于 1967 年分别独立解决了这个问题，而且算法与排序后扫描边的做法毫无相似之处：它为每个顶点选出最便宜的入弧，然后收缩形成的环，并重复这一过程。

10. 如何选择：你的关系是对称的吗？

建模问题只有一种形式：如果关系从 u 到 v 成立，它是否必须从 v 到 u 也成立？如果是，就用无向图。如果不是，或者你不确定，就用有向图，因为有向图总能表达对称关系，反之则不行。

有一种情况值得特别注意，因为它看似对称，其实不然。一条无向边只能承载一个权重。如果从 u 到 v 的成本与返回的成本不同，这种关系虽然是相互的，模型却仍必须是有向的。骑车上坡与下坡、在不对称链路上的上传与下载、以及朝不同方向兑换货币，都是成本不同的相互连接，每一种都要求使用带有两条不同权重弧的有向图。

11. 两者之间的转换

有三种转换经常出现，每一种都会丢失或凭空制造一些你应当注意的东西。

• 有向图转无向图（对称化）。把每条弧换成一条边。这会凭空制造可达性：对贯穿示例进行对称化后，D 能到达 A，而这在原图中是错误的。只有当你确实想询问底层结构的问题时才使用它，例如有向图是否弱连通。更严格的变体只保留互相连接的对，得到“互惠”图，它不制造任何东西，但丢弃了大量信息。
• 无向图转有向图（定向）。为每条边选定一个方向。除非图没有桥，否则这会破坏相互可达性，这正是第 6 节中的 Robbins 定理。
• 把无向图当作有向图（弧加倍）。把每条边 {u, v} 换成两条弧 (u, v) 和 (v, u)。几乎每个图库在内部都是这样做的，对遍历和最短路径来说这是忠实的。但它让每条边都变成长度为 2 的有向环，因此任何 DAG 检验现在都会给出否定答案，每个连通分量都变成一个强连通分量，环检测器会为每一条边都报告一个环。这种表示本身没问题；在它上面运行有向结构算法才有问题。

12. 常见错误

• 为无向图只单向构建邻接表。这恐怕是世上最常见的图算法 bug。读取边列表时只执行 adj[u].push(v) ，会悄无声息地得到一个有向图，然后你的 BFS 就找不到沿着一条它明明看得见的边的路径。
• 为有向图双向构建邻接表。同样的错误反过来，而且更难发现：代码能运行，路径看起来也合理，但所有依赖方向的答案都是错的。
• 在有向图上使用无向环检测。只要 DFS 遇到非父节点的已访问顶点就报告环，会把许多 DAG 误判为有环。有向图需要检验指向递归栈的回边。
• 假设可达性是对称的。 “是否存在从 u 到 v 的路径”和“是否存在从 v 到 u 的路径”在有向图中是两个不同的查询，回答了一个并不等于回答了另一个。
• 忘记需要反向图。 “哪些顶点能到达 v”无法仅凭正向邻接表在少于一次完整扫描的代价内回答。如果你经常问这个问题，就预先构建一次反向表。
• 在有向图上求最小生成树。 Kruskal 和 Prim 算法没有有向版本。你需要的是最小树形图。
• 为了复用图库而对称化。这很方便，但会改变答案。第 11 节中的每种转换都有代价，所以要有意识地使用。

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Robbins, H. E. (1939). "A theorem on graphs, with an application to a problem of traffic control." American Mathematical Monthly 46(5)，281 至 283 页。即第 6 节中的无桥定向定理。
2. Ford, L. R. and Fulkerson, D. R. (1956). "Maximal flow through a network." Canadian Journal of Mathematics 8，399 至 404 页。从一开始就在有向图上提出流问题。
3. Nash-Williams, C. St. J. A. (1960). "On orientations, connectivity and odd-vertex-pairings in finite graphs." Canadian Journal of Mathematics 12，555 至 567 页。Robbins 定理向 k-弧连通的推广。
4. Kahn, A. B. (1962). "Topological sorting of large networks." Communications of the ACM 5(11)，558 至 562 页。
5. Chu, Y. J. and Liu, T. H. (1965). "On the shortest arborescence of a directed graph." Scientia Sinica 14，1396 至 1400 页。
6. Harary, F., Norman, R. Z. and Cartwright, D. (1965). Structural Models: An Introduction to the Theory of Directed Graphs. 纽约：Wiley。强连通、单向连通、弱连通分类的出处。
7. Edmonds, J. (1967). "Optimum branchings." Journal of Research of the National Bureau of Standards 71B(4)，233 至 240 页。
8. Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing 1(2)，146 至 160 页。线性时间的强连通分量算法。
9. Sharir, M. (1981). "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications 7(1)，67 至 72 页。通常与 Kosaraju 之名并称的两遍算法。
10. 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 页。网页有向图上的 PageRank。
11. West, D. B. (2001). Introduction to Graph Theory，第 2 版。Upper Saddle River：Prentice Hall。
12. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244。伦敦：Springer。
13. Bang-Jensen, J. and Gutin, G. (2009). Digraphs: Theory, Algorithms and Applications，第 2 版。伦敦：Springer。有向图术语的标准参考书。
14. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms，第 3 版。马萨诸塞州剑桥：MIT Press。即第 4 节中表示成本的出处。
15. Chartrand, G., Lesniak, L. and Zhang, P. (2015). Graphs & Digraphs，第 6 版。Boca Raton：CRC Press。一本并列讲解两种对象的教材。
16. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。即第 1 节中所引两种定义的出处。