从关系到图：节点和边从哪里来

一个网站有四个模块：页面 P、推荐 G、特征 F、存储 S。页面直接使用推荐和特征，推荐使用特征，特征再从存储读取数据。

现在准备修改存储模块。有人翻遍页面代码，说：“页面没有直接调用存储，应该不用检查它。”另一个人却担心页面会受影响。两人看到的代码可以都没错，分歧藏在“有关”这个词里：一个说的是直接使用，另一个说的是沿着依赖关系间接联系。

画几条线就能解决吗？先别急。我们必须约定线究竟代表什么，再谈怎样顺着线推理。本章要从这项约定出发，把上一章的集合变成图，并看清图能保留什么、推出什么。

1 先把关系写成可以核对的记录

把研究对象放进集合：

V = {P, G, F, S}

这里把每个模块当成一个对象，暂时不拆开模块内部的函数。再规定“x 直接使用 y”为我们唯一记录的关系。

用有序对 (x, y) 记一条记录。括号里先后顺序有意义：(P, G) 表示页面使用推荐；(G, P) 表示推荐使用页面，二者是不同的事。“有序”只强调位置，不表示时间早晚。

于是，全部记录可以写成：

R = {(P, G), (P, F), (G, F), (F, S)}

V 中任取一个对象放前面，再任取一个放后面，共有 4 × 4 = 16 种有序对，包含 (P, P)。全部可能的有序对组成 V × V，读作“V 与 V 的笛卡尔积”。这里的乘号表示配对集合。

R 从这些可能的配对里选出关系成立的那些，数学上写作 R ⊆ V × V，称为 V 上的二元关系。“二元”说的是每条记录涉及两个位置，不要求这两个位置一定放不同对象。

这也接上了上一章的命题：给定 x 和 y，“x 直接使用 y”就能判断真假；关系 R 收集所有判断为真的配对。1

2 每个对象画成点，每条记录画成箭头

把 V 中的对象各画成一个节点，也叫顶点；把 R 中的 (x, y) 画成 x → y，这就得到一个有向图。我们用 H = (V, E) 记整个图：V 是顶点集合，E 是边集合，此处 E 就取 R。

图1：移动节点、弯曲边，并没有改变“谁直接使用谁”。

左图像分层架构，右图像一个环形布局。逐条检查，两张图都只有 P → G、P → F、G → F、F → S 四条边。线段画得更长，不代表调用更慢；两条线在纸上交叉，也不会自动增加一个节点。

给定顶点集合和这项关系，在不允许重复边的约定下，可以从记录画出图，也可以从图恢复记录。对象间的直接关系没有丢失。没有任何关系的对象也要保留成孤立节点，单记边的清单可能漏掉它。页面代码的细节、模块所在服务器、团队负责人则从未被记入，当然无法凭空读出来。

箭头、圈和数字要按问题选择

“互为邻居”通常是对称关系，可以画无向边 {x, y}，端点不分先后。如果改用有序对记录，就需要同时写 (x, y) 和 (y, x)。模块依赖可能只有单向，不能随意擦掉箭头。

(x, x) 对应自环，即从节点出发又指向自己的边。本例没有自环；若节点表示状态，“收到一个无须处理的消息后仍处于原状态”就可能需要自环。

要区分连接耗时，可以给边加权重，但必须说明数字的意义和单位。标上“20 毫秒”，还要说明是某次测量、平均值还是上限；一个数字不能自动保证运行时表现。

若两个模块既通过 HTTP 请求交互，又通过消息队列交互，而问题要求保留这两种通道，就需要两条端点相同的边，即多重边。此时单靠有序对的集合会把它们合并，必须额外记录边的身份或类型。2

下面仍使用最初那个没有自环、没有多重边的有向图。选择简单形式，是因为当前只问“是否直接使用”。

3 相邻只看一步，可达允许接着走

P → F 是一条边，所以 F 是 P 的一个出邻居；这个“出”字提醒我们遵守箭头方向。P 与 S 没有直接边，但可以顺着 P → F → S 走过去。

为免日常说法混淆，这里明确术语约定：

• 游走：沿箭头接连经过若干条边，允许重复经过节点和边
• 路径：不重复节点的游走，也常叫简单路径
• 长度：经过的边数，暂时不计算权重
• 可达：从起点到终点存在一条游走

不同教材对“路径”的用法略有差别；本章遵循上面的约定。P → G → F → S 是长度为 3 的路径，P → F → S 是长度为 2 的路径。反过来，从 S 出发没有边可走，因此 P 从 S 不可达。1

我们也允许长度为 0 的游走：停在原点，不走任何边。因此每个节点都从自身可达，即使没有自环。“走过至少一条边后回来”是另一个问题，不能拿零步作答。

原来的 R 记录直接使用；把所有可达配对收集起来，又得到一个关系。这个新关系包含 (P, S)，原来的 R 却不包含它。把“间接也有关”混入直接边，会改变图所表达的事实。

4 一个可以亲手检查的结论

命题：在有 n 个顶点的有限有向图中，如果从 u 可以到达 v，就存在一条从 u 到 v、长度不超过 n − 1 的路径。

这里 n 至少为 1；当 u = v 时，零步路径已经满足结论。对于不同的起终点，先拿出任意一条确实走得到的游走。

如果它重复经过某个节点 x，就找到两次到达 x 的位置。两次之间的那段绕行从 x 出发又回到 x。删掉整段绕行后，前半段仍停在 x，可以直接接上后半段原本从 x 出发的边，终点不变。

图2：另取一个含回路的小图，删掉绕行仍然可以到达原终点。

每删一次，边数至少减少 1。原来的边数是有限的，所以不可能无止境地删。最后没有重复节点，得到一条路径。图中一共只有 n 个顶点，路径最多经过 n 个；连接这些顶点最多需要 n − 1 条边。证明完成。1

这告诉我们：判断纯粹的可达性时，绕圈不会成为必需条件。它给出了一个有限长度的见证上界，但还没告诉我们怎样高效找到这条见证。

条件也很重要。假如绕一圈能够拿到钥匙，那么“回到同一个房间”未必回到了同一个状态。若后续通行取决于钥匙，就要把“房间位置、是否持有钥匙”一起作为节点内容。证明没有失效，原来只记录房间的模型漏掉了影响行动的信息。

5 计算机可以不画图

纸上的点和线便于理解，程序更适合保存明确的记录。仍以 P、G、F、S 为顺序，可以写一张表：行表示起点，列表示终点，有边填 1，没有填 0。

这叫邻接矩阵。现在只把它看成有固定行列的记录表，不需要先学线性代数。P 行 S 列为 0，仍然不妨碍 P 到 S 可达，因为这张表仅记录一步。

另一种方式是邻接表：给每个顶点列出它能直接指向的顶点。2

图3：同一条 P → F，在矩阵中占一个格，在邻接表中占一个条目。

邻接矩阵给每一种可能的配对留位置，n 个顶点就有 n × n 个格。若有一万个顶点，即使只有两万条边，也需要一亿个格。邻接表保留一万份顶点入口和两万条边记录，在这样的稀疏关系里通常更节省空间；具体字节数取决于实现。

要检查某条边是否存在，矩阵可直接查一个格；要列出某个节点的所有出邻居，邻接表可以直接读取那份名单。二者表达同一张图，却让不同操作更方便。这是数据结构选择的一个早期例子。

6 图给出检查范围，结论还需要更多内容

回到开头。P 能到达 S，表明页面对存储存在一条依赖链，因此页面属于值得检查的范围。沿我们的箭头是寻找依赖；从存储查哪些模块可能受影响，则要反着追踪。

但“可能受影响”不等于“必然出错”。存储可能保持了接口兼容，调用也可能发生在本次没有执行的分支。单凭这四条边，无法推断故障概率或响应时间。

我们还假设这份关系清单是完整的。如果只从一次运行日志里收集调用，没看到一条边，可能只是那段代码没有执行。此时矩阵里的 0 表示“尚未观察到”，就不能直接当成“确实不存在”。

AI 系统也会记录计算之间的依赖。例如 y = (a + b) × c，可以把加法、乘法及其输入输出组织成计算图。PyTorch 的自动求导会记录实际执行的运算，并利用这些记录计算梯度，也就是描述输入的微小变化如何影响结果的变化率。3 图的连接关系说明谁依赖谁，运算类型和保存的数据才进一步决定怎样计算；擦掉“加”与“乘”等信息，只剩箭头骨架，就不足以恢复结果。

图的价值在于把一项明确的关系保存下来，让原本藏在叙述中的连锁联系变得可检查。下一章会进一步追问：当程序一步步改变状态时，有哪些性质能够始终成立？

顺手试一下

题目1：一条新增的边

给最初的四模块图增加 S → G。现在 S 能否到达 P？F 能否经过至少一条边回到 F？请分别给出理由。

**提示：**从 S 开始顺箭头走；不要因为图里出现了圈，就认为所有节点都相互可达。

**参考答案：**S 不能到达 P，因为没有任何边指向 P，而 S 与 P 不同。F 可以沿 F → S → G → F 返回，长度为 3。这是重复了起终点的游走，不是本章定义的路径。

题目2：把箭头擦掉会怎样

仍用最初的四模块图。若把全部边改成无向边，“S 能到达 P”的答案会改变吗？这说明什么？

**提示：**试走 S、F、P。

**参考答案：**会。无向图中可以沿 S—F—P 到达；原有向图中却不行。擦掉方向丢失了依赖关系的信息，所得结果不能继续解释为原来的“沿直接使用关系追踪”。

延伸阅读与来源

1 Eric Lehman、F. Thomson Leighton、Albert R. Meyer，《Mathematics for Computer Science》，MIT，2015。参见4.4节的二元关系、9.2节的游走与路径、9.4节的可达关系。本章采用其不重复顶点的路径约定。

2 Robert Sedgewick、Kevin Wayne，《Algorithms, 4th Edition》配套材料第4.2节。参见有向图、自环、平行边，以及邻接表和邻接矩阵的表示。该教材对 path 的术语约定与本文不同，阅读时留意定义。

3 PyTorch 官方文档，Autograd mechanics，参见“How autograd encodes the history”。本章只借此说明计算依赖需要连同运算信息保存，自动求导的计算规则留待后文。

作者：Jiancheng Wang · 数学之美（独立原创）