02.08 图与依赖遍历：从用户关系到任务拓扑
返回第二卷 · 集合前置：02.04 · 队列前置：02.02 · 堆前置：02.07
02.08 图与依赖遍历：从用户关系到任务拓扑
DeepTutor 初稿经技术与教学审阅后的静态课程。用户、关系和处理步骤均为虚构模型，没有运行 Go、IM 服务、数据库或基准。关系上的“可达”不等于拥有读取消息的权限；任务依赖的拓扑顺序也不等于任务已执行或消息已送达。
一、把一对多关系说清：图的词汇与两种方向
02.06 的树有根和父子关系，02.07 的堆还限定完全树形。IM 中另有更一般的问题：用户关系可交叉连接，处理步骤可汇合和分叉，未必有唯一父节点。图用顶点表示对象，用边表示对象之间被明确定义的关系；路径是由相邻边连接的一串顶点。数据中有没有边，是建模与权限范围内的问题，不能靠图算法凭空推断。
本章使用两张纸图。第一张是六个虚构用户的无向关系图：u-a—u-b、u-a—u-c、u-b—u-d、u-c—u-d、u-d—u-e，u-f 暂无边。无向表示本章的练习关系在两端对称；它不是产品好友或会话授权规则。第二张是五个抽象步骤的有向依赖图：A→B、A→C、B→D、C→D、D→E；箭头 X→Y 表示 Y 必须等 X 的前置条件完成。箭头反向不成立。
先识别三个问题：从 u-a 能否沿边到 u-e，最少要经过几条边？从 u-a 能否到 u-f？抽象任务 D 要等哪些直接前置步骤？前两个用遍历和可达性回答，第三个要按有向边读依赖。路径长度在本章按经过的边数计；后续 02.09 才给边加成本。
| 第一遍 | 第二遍 | 交付物 |
|---|---|---|
| 顶点、边、方向、邻接表、访问标记 | BFS/DFS、连通与环、拓扑顺序、成本和输入边界 | 两张邻接表、BFS/DFS 状态表、一张有向依赖评审图 |
二、邻接表：先约定一条边如何落在数据里
邻接表给每个顶点保存直接相连的邻居。为使纸上结果可复核，下面各表按顶点 ID 排序；实际 Go map 的遍历次序不能当作这个排序合同。无向边要在两端的列表中各出现一次，孤立顶点也要保留一个空列表。
| 顶点 | 有序邻居 |
|---|---|
u-a | u-b, u-c |
u-b | u-a, u-d |
u-c | u-a, u-d |
u-d | u-b, u-c, u-e |
u-e | u-d |
u-f | 空 |
Go 初学者可把纸图想成 map[string][]string：键是顶点 ID，切片是相邻 ID。map 给出“按 ID 找邻居列表”的能力，不替列表定义遍历顺序。若要固定 BFS/DFS 的纸上访问序列，应对邻居显式排序或按约定输入顺序保存。若关系对称，读取数据时还要拒绝未知顶点、重复边和不允许的自环，并检查两端记录一致。
有向依赖图只沿箭头保存：A:[B,C]、B:[D]、C:[D]、D:[E]、E:[]。不能因为 D 出现在 B 的列表，就把 B 放进 D 的出边列表。D 确有 B、C 两条入边，但入边与出边回答不同问题。
邻接表保存每个顶点和实际边，空间随 V+E 增长；无向边两端都记录，但仍是同一数量级。若用 V×V 的邻接矩阵，查询某对顶点有无边可按下标直接看一个格子，空间却是 O(V²)；对于用户很多、关系较稀疏的纸图，邻接表更适合入门。V 是顶点数，E 是边数；无向边按一条计数时，本例 V=6、E=5。
三、BFS：队列按距离层次扩展，标记防止重复入队
广度优先搜索（BFS）从起点开始，先看一条边可达的邻居，再看两条边可达的顶点。它需要 02.02 的 FIFO 队列和 02.04 的已访问集合。把 u-a 标记为已发现，距离 dist[a]=0，入队；每取出一个顶点，按有序邻居列表查看未发现者，在入队时立刻标记、记父节点与距离 dist[child]=dist[parent]+1。
| 取出前队列 | 取出 | 新发现与记录 | 取出后队列 |
|---|---|---|---|
[u-a] | u-a | u-b: parent=a, dist=1；u-c: parent=a, dist=1 | [u-b,u-c] |
[u-b,u-c] | u-b | u-a 已标；u-d: parent=b, dist=2 | [u-c,u-d] |
[u-c,u-d] | u-c | u-a、u-d 已标 | [u-d] |
[u-d] | u-d | u-b、u-c 已标；u-e: parent=d, dist=3 | [u-e] |
[u-e] | u-e | u-d 已标 | [] |
取出顺序是 u-a,u-b,u-c,u-d,u-e。u-f 从未发现，因此从 u-a 不可达；这不意味着它不是顶点。由 parent 反推 u-e←u-d←u-b←u-a，可得一条三边路径 u-a→u-b→u-d→u-e。若邻居顺序改了，也可能取经 u-c 的三边路径，距离仍为 3。
为何 BFS 得到无权图的最少边数？距离为 k 的顶点出队时，队列里后续新增的邻居距离为 k+1；FIFO 保证较浅层先于更深层处理。一个顶点第一次被发现时，不会存在尚未处理的更短层路径。标记若拖到出队时，u-d 可从 u-b 与 u-c 各入队一次；入队即标记才保证一次发现。这个“最短”只按边数；若一条边耗时 1 ms、另一条 1 s，BFS 不会据此找最低时延路径。
四、DFS：沿一条路走到底，回退后再看别的分支
深度优先搜索（DFS）也用已访问集合，却用递归调用栈或显式栈保存“走到哪里、还有哪些邻居没看”。对同一张无向图，按有序邻居递归，进入顶点时就标记：从 u-a 先到 u-b，再到 u-d；D 的 u-b 已见，先走 u-c，C 的 u-a、u-d 都已见，返回 D，再走 u-e。首次进入顺序是 u-a,u-b,u-d,u-c,u-e，u-f 仍不可达。
进入 u-a
进入 u-b
进入 u-d
进入 u-c → 邻居已见，回退
进入 u-e → 邻居已见，回退DFS 可回答可达性，也能保留 parent 给出某一条路径；但首次找到的路径不保证边数最少。例如先沿 u-a→u-b→u-d→u-c 找 u-c 是三边，图中其实有直接边 u-a—u-c。这正说明“能找到路径”与“找到最少边路径”不同。改变邻居访问顺序会改变 DFS 序列和首次路径；若结果要求复现，要固定该顺序。
对深图，递归实现会占用与搜索深度相关的调用栈；显式栈能把这份状态转为受控的数据结构，但同样需要明确容量和失败处理。一个 map[string]bool 只表达是否访问，若要精确模拟迭代式 DFS 的递归顺序，还需保存每个顶点的下一个邻居位置。
五、连通与环：无向父边和有向活动路径不要混用
从 u-a 可访问 {u-a,u-b,u-c,u-d,u-e}，而 u-f 自成另一块。对无向图，每一块任意两点可相互到达的顶点集叫连通分量；本例有两个。若要列出整个图的分量，需要对尚未访问的顶点重新启动遍历，因此最后会从 u-f 启动一次。单次从 u-a 的遍历只覆盖它所在的一块。
无向图还存在环 u-a—u-b—u-d—u-c—u-a。但从 u-b 看见已访问的 u-a，只是沿原边返回父节点，不是一个新环的证据。对无向 DFS，看到已访问且不是当前父节点的邻居才提示环；本例从 u-c 看见 u-a 可形成上述环。
有向依赖图的环要按箭头方向找。原图 A→B/C→D→E 无环；若再加 E→B，就出现 B→D→E→B，所有箭头方向均能连起来。用有向 DFS 查环时，可区分白（未发现）、灰（在当前活动递归路径上）、黑（已完成）：沿出边遇到灰顶点是指向活动祖先的回边，表明有向环；遇到黑顶点只表示另一条已完成路径汇合，不能直接判环。无向图的“排除父边”和有向图的“灰色回边”是两套判据。
六、拓扑顺序：让所有前置排在后置之前
给有向无环图中的抽象任务定义：A=读取输入，B=范围检查，C=格式检查，D=记录决策，E=输出结果。依赖是 A→B、A→C、B→D、C→D、D→E。若 B 或 C 检查失败，实际业务可停止后续；图只描述允许执行的前置关系，不代替分支合同。
拓扑顺序是一个顶点列表，使每条边 X→Y 的 X 都排在 Y 前。本图的 A,B,C,D,E 与 A,C,B,D,E 都合法：B 和 C 谁先都行，D 必须等二者，E 必须排在 D 后。A,B,D,C,E 不合法，因为 C→D 被颠倒。若加入 E→B 构成 B→D→E→B，B 要先于 D、D 要先于 E、E 又要先于 B，不可能排出拓扑顺序。
一种纸上算法反复取入度为零的顶点：开始只有 A；移除 A 的出边后 B、C 入度降为零；取完 B、C 后 D 才为零；最后 E。若仍有顶点和边却再也没有入度零顶点，就存在环。也可用 DFS 的完成顺序推导拓扑序，但必须先排除有向环。无论哪一种，拓扑顺序是结构约束，不是实际线程调度、事务提交或消息交付保证。
七、成本、边界与 IM 迁移
用邻接表遍历整张图时，每个顶点最多被标记一次，每条有向边最多查看一次；无向边会从两端各查看一次，仍是 O(V+E) 量级。队列、栈和标记集合至多随 V 增长；邻接表本身占 O(V+E)。从 u-a 单次搜索只访问可达分量；说整图复杂度时应把从 u-f 等未访问顶点重启的工作也算进去。矩阵表示若对每个访问顶点都扫描整行，通常是 O(V²)。
| IM 需求 | 图能回答的纸上问题 | 图不能代替的业务检查 |
|---|---|---|
| 虚构用户关系 | 从 u-a 是否沿定义的边到 u-e、最少几跳 | 当前用户能否读取某会话、是否已退群 |
| 步骤依赖 | D 的前置 B/C 是否都排在它之前、是否有环 | 输入校验是否成功、执行是否成功 |
| 大群处理 | 关系规模和可能遍历量如何随 V/E 增长 | 真实扇出、设备状态、资源限额和交付确认 |
现实图可能在遍历时更新。若先后读到不同版本的边，纸上“同一张图”的推导前提就不成立；要先约定快照、版本或容忍的变化范围。更不能把“图上两点相连”直接变成授权决定；授权仍要按当前身份、会话成员和对象范围检查。动态权重、最低成本路径及剪枝在需要时进入 02.09；海量群负载与运行证据留给 S4 后续。
八、交付两张图和分层练习
交付一张无向邻接表和一张有向邻接表；在无向图上逐步列出 BFS 的队列、visited、parent、dist，再列 DFS 首次访问次序、两个连通分量及四边环；在依赖图上列两种合法拓扑顺序，并解释加 E→B 后失败。全部是纸上模型，不把结果写成真实 IM 权限或投递结论。
分层练习：先答，再展开反馈
1. 顶点与边各表示什么？
顶点表示对象，边表示预先定义的对象关系；边的含义要由业务给定。
2. `u-a—u-b` 与 `A→B` 的方向有什么差别？
前者在练习图中双向相邻；后者只表示 A 指向 B，不能反读。
3. 无向边 `u-a—u-b` 在邻接表中记几端？
两端各记一次，u-a 的邻居含 u-b，u-b 的邻居含 u-a。
4. `u-f` 没有边，还算一个顶点吗？
算。它要有空邻居列表，才能在整图遍历中被发现为独立分量。
5. 本例无向图的 V、E 各是多少？
V=6，E=5；无向边按一条计，邻接表会写两端。
6. Go `map` 遍历可直接承诺邻居访问顺序吗？
不能。要复现固定序列，需显式排序或固定切片次序。
7. BFS 使用队列还是栈？
使用 FIFO 队列，先扩展较浅距离层。
8. BFS 为什么在入队时标记 `u-d`？
避免 u-b 与 u-c 都把同一个 u-d 再次加入队列。
9. 从 u-a 的 BFS 取出顺序是什么？
按本章邻居顺序是 u-a、u-b、u-c、u-d、u-e。
10. 从 u-a 到 u-e 的最少边数是多少？
3；可经 u-b 或 u-c 到 u-d，再到 u-e。
11. BFS 是否找到最低网络时延的路径？
不一定。这里每条边只按一步计，没有时延权重。
12. DFS 按排序邻居首次进入次序是什么？
u-a、u-b、u-d、u-c、u-e。
13. DFS 首次找到 u-c 的路径一定最少边吗？
不一定。它可能先走 u-a→u-b→u-d→u-c，而直接边 u-a—u-c 更短。
14. 从 u-b 看见父节点 u-a 就能判无向环吗？
不能，那是沿原无向边返回父节点；要排除父边。
15. 本例的一个无向环是什么？
u-a—u-b—u-d—u-c—u-a。
16. 本例无向图有几个连通分量？
两个：{u-a,u-b,u-c,u-d,u-e} 和 {u-f}。
17. 有向 DFS 遇到灰色与黑色顶点有什么不同？
灰色在当前活动路径上，指向灰色的回边构成有向环；黑色已完成，汇合并不足以判环。
18. A,B,C,D,E 是合法拓扑序吗？
是。A 在 B/C 前，B/C 都在 D 前，D 在 E 前。
19. A,B,D,C,E 为何不合法？
边 C→D 要求 C 在 D 前，该列表把 D 放到了 C 前。
20. 加 E→B 后的有向环是什么？
B→D→E→B，因此没有拓扑顺序。
21. 邻接表遍历整图的主要成本是什么？
O(V+E)；每个顶点及其邻边按常数次数处理。
22. 图上 u-a 能到 u-e，能据此允许读 c-a 历史吗？
不能。图可达只针对定义的关系，读取权限仍需当前身份、会话成员及对象范围规则。
来源与下一步
- Princeton《Algorithms》无向图：邻接表、DFS、BFS、路径与连通性。
- Princeton《Algorithms》有向图：有向环、DAG 与拓扑顺序。
- MIT 6.006 BFS 课程及课程讲义：图表示、BFS、DFS 与拓扑的课程前置。
按学习路线，S4 主线下一章是03.05 虚拟内存；需要比较带权路径时再回到02.09 加权路径与状态空间，区分最少跳数与最低代价。离开本章前，应能独立说出什么是边、何时标记、BFS/DFS 各保证什么、何种环阻止拓扑顺序，以及图结果不能替代哪项 IM 业务检查。