04 · 图与并查集

图是最"通用"的结构——链表、树都是图的特例。这一篇的重点不是背算法，是知道什么场景该用哪个。

一句话本质

• 图：表达"多对多关系"。树只能"一个爹"，图可以互相连。
• 并查集：只回答一个问题——"这两个东西是不是一伙的"，而且回答得极快。

生活类比

结构/算法	场景
图	地铁线路图：站点之间互相连通
邻接矩阵	一张"谁和谁相邻"的表格，格子打勾
邻接表	每个人的通讯录：我认识谁，一个个列出来
BFS	水波纹扩散：一圈一圈往外
DFS	走迷宫：一条路走到黑，撞墙退回
拓扑排序	穿衣服：内衣必须在衬衫前，衬衫必须在外套前
Dijkstra	导航找最快路线
并查集	判断两个人是不是同一个家族的（顺着族谱往上找同一个祖先）

核心机制

一、两种表示法

邻接矩阵：matrix[i][j] = 权重（无边则 ∞ 或 0）

      A  B  C  D
  A [ 0  1  1  ∞ ]
  B [ 1  0  ∞ 1  ]
  C [ 1  ∞  0 1  ]
  D [ ∞  1  1  0  ]

优点：判断"i 和 j 是否相邻" O(1)；适合稠密图
缺点：空间 O(V²)；稀疏图浪费严重

邻接表：adj[i] = [邻居1, 邻居2, ...]

A > [B, C]
B > [A, D]
C > [A, D]
D > [B, C]

优点：空间 O(V + E)；适合稀疏图（实际绝大多数图都是稀疏的）
缺点：判断"是否相邻"要遍历邻居列表

怎么选：边数接近 V² 用矩阵，否则用表。实际工程几乎都用邻接表。

二、BFS 与 DFS：唯一的区别是"用队列还是栈"

BFS（队列）：
  起点入队
  while 队列非空：
    取出队头 u
    for v in u 的邻居：
      if v 未访问：标记、入队

DFS（栈 / 递归）：
  dfs(u)：
    标记 u
    for v in u 的邻居：
      if v 未访问：dfs(v)

两者都能遍历全图，差别在"访问顺序"决定了它们适合什么：

	BFS	DFS
数据结构	队列	栈 / 递归
找到的路径	最短（边数最少）	不保证最短
适合	最短路径（无权图）、层序遍历、找最近	连通性、拓扑排序、环检测、回溯
空间	O(宽度)，可能很大	O(深度)，可能很深（爆栈）

关键结论：无权图的最短路径用 BFS。这是最高频的应用判断。

三、拓扑排序：只适用于有向无环图（DAG）

任务依赖：
  A > B  （A 完成后才能做 B）
  A > C
  B > D
  C > D

拓扑序：A B C D  或  A C B D   （不唯一）

Kahn 算法（BFS 版）：

① 统计每个节点的入度
② 入度为 0 的入队
③ 出队，输出，把它的邻居入度减 1；减到 0 的入队
④ 重复直到队列空
⑤ 如果输出的节点数 < 总数 > 有环（无法拓扑排序）

DFS 版：后序遍历的反转就是拓扑序。

用途：编译依赖、任务调度、课程安排（先修课）、Maven/Gradle 的构建顺序。第 ⑤ 步"输出数 < 总数就说明有环"，是检测环的标准方法。

四、最短路：三个算法对应三种场景

算法	解决什么	复杂度	限制
BFS	无权图单源最短路	O(V+E)	只能无权
Dijkstra	非负权单源最短路	O((V+E)log V) 用堆	不能有负权边
Bellman-Ford	可有负权的单源最短路	O(VE)	慢，但能检测负环
Floyd	全源最短路	O(V³)	只能小图

Dijkstra 的核心思想（贪心）：

① 起点距离 0，其他 ∞
② 每次从未确定的节点中，选距离最小的那个，标记为"已确定"
③ 用它去松弛邻居：if (dist[u] + w < dist[v]) dist[v] = dist[u] + w
④ 重复直到所有节点确定

为什么不能有负权：Dijkstra 假设"已经确定的最短距离不会再变短"。但负权边可以让"绕远路"反而更短，这个假设就破了。

为什么用堆优化：第 ② 步要"取最小值"，用堆就是 O(log V)；朴素实现是 O(V) 遍历。

五、并查集：只做两件事

// 找根（带路径压缩）
int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);  // 路径压缩
    return parent[x];
}

// 合并（按秩/大小合并）
void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return;
    if (rank[ra] < rank[rb]) parent[ra] = rb;
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
}

// 判断是否同集合
boolean connected(int a, int b) { return find(a) == find(b); }

两个优化，缺一不可：

1. 路径压缩：查找时把路径上所有节点直接挂到根上。下次查找就是 O(1)。
2. 按秩合并：矮树挂到高树下，避免树变高。

两个都做，复杂度是 O(α(n))——α 是反阿克曼函数，实际取值 ≤ 4。可以认为是 O(1)。

典型用途：判断连通性（网络节点是否连通）、Kruskal 最小生成树、朋友圈/亲戚关系、检测无向图环。

为什么不用 DFS/BFS 判断连通：并查集支持动态加边（边一条条来，随时问连通性），而 DFS 每次都要重跑 O(V+E)。并查集单次操作接近 O(1)。

六、最小生成树（了解）

Prim：从一个点开始，每次选"连接已选集合和未选集合的最短边"——像 BFS + 贪心。 Kruskal：把所有边排序，从小到大加，用并查集判断"加了会不会成环"——并查集的经典应用。

为什么这么设计

反事实 1：如果没有图结构，怎么表达"多对多"

用二维表（关系型数据库）——但查询"从 A 到 B 有几条路径"要反复 join，极其低效。图把"关系"变成"一等公民"，遍历就是顺着边走。

反事实 2：如果并查集不做路径压缩

树会越来越深，find 变成 O(n)。100 万次查询就是 O(n²)，直接超时。

路径压缩的妙处：它把"查找"这个操作顺带变成了"优化结构"的操作——每次查询都在让下次查询更快。

反事实 3：如果 Dijkstra 允许负权

A > B 权重 1
A > C 权重 5
C > B 权重 -10

Dijkstra 的步骤：
  选 A（0），松弛得 B=1, C=5
  选 B（1）> 标记确定，认为"到 B 的最短距离就是 1"
  选 C（5）> 松弛 B：5 + (-10) = -5 < 1 ！
  > 但 B 已经被标记"确定"了，不会再更新 > 结果错误

正确结果应该是 A>C>B = -5。所以有负权必须用 Bellman-Ford（它允许反复松弛，V-1 轮后收敛）。

面试怎么问

Q：BFS 和 DFS 的区别？各用在哪？

数据结构不同（队列 vs 栈），访问顺序决定用途：BFS 找无权图最短路、层序；DFS 找连通性、拓扑排序、回溯。 加分：BFS 空间是 O(宽度)，DFS 空间是 O(深度)，稠密图 BFS 可能爆内存，长链 DFS 可能爆栈。

Q：拓扑排序怎么实现？怎么检测环？

Kahn 算法：统计入度 > 入度 0 入队 > 出队减邻居入度 > 如果最终输出的节点数少于总数，说明有环。

Q：Dijkstra 为什么不能处理负权边？

因为它基于贪心假设"已确定的最短距离不会再变短"。负权边可能让"绕远路"更短，破坏这个假设。用 Bellman-Ford。

Q：并查集的两个优化是什么？

路径压缩（查找时把路径上所有节点挂到根）+ 按秩合并（矮树挂高树下）。两者结合复杂度 O(α(n))，接近 O(1)。

追问链：

怎么判断两个节点连不连通？
  > BFS/DFS 可以，但每次要重跑 O(V+E)
    > 如果边是动态加的？（并查集）
      > 并查集为什么快？（路径压缩 + 按秩合并）
        > 那有向图的连通性呢？（并查集不行，要用强连通分量 Tarjan）
          > 最短路径呢？（无权 BFS / 非负权 Dijkstra / 有负权 Bellman-Ford）

和其他知识的连接

• < 来自 栈、队列与哈希表：BFS 用队列，DFS 用栈，拓扑排序用队列/栈
• < 来自 树与堆：树是图的特例；Dijkstra 用优先队列（堆）优化
• > 影响 工程实践：依赖管理（Maven/npm）、任务调度 DAG、社交网络推荐、地图导航、编译器的控制流图
• > 影响 锁与死锁：数据库死锁检测就是"在等待图里找环"，和拓扑排序检测环是同一套思路
• > 影响 分布式：一致性哈希环、服务依赖图、链路追踪

自测 3 问

Q1：为什么无权图的最短路用 BFS，而不是 DFS？

点开看答案

因为 BFS 是按层扩展的：先访问所有距离为 1 的节点，再访问距离为 2 的，以此类推。

所以第一次访问到目标节点时，走的边数一定是最少的——所有更短的路径都在更早的层，已经访问过了。

DFS 是"一条路走到黑"，可能先走了一条很长的路到达目标，虽然存在更短的路径，但它先返回了长的那条。

前提：无权（或所有边权相同）。一旦有权重，"层数少"不等于"总权重小"，就必须用 Dijkstra。

Q2：并查集能不能判断有向图的连通性？

点开看答案

不能。

并查集处理的是无向的"等价关系"——它假设"a 和 b 连通"是对称的（a 能到 b，b 也能到 a）。

有向图里，a 能到 b 不代表 b 能到 a。并查集合并后就丢失了方向信息，无法正确判断。

有向图的连通性要用：

• 强连通分量（Tarjan / Kosaraju）：a 和 b 互相可达。
• 可达性：BFS/DFS，或者传递闭包（Floyd）。

Q3：Kruskal 为什么要用并查集？

点开看答案

因为 Kruskal 的核心判断是："这条边的两个端点，是否已经在同一个连通块里？"

• 如果已经在同一个块里 > 加这条边会形成环，必须跳过。
• 如果不在 > 加上它，两个块合并。

这正是并查集的两个操作：find(a) == find(b) 判断，union(a,b) 合并。

而且 Kruskal 是按边权从小到大处理的，边一条条加、随时要判断连通性——正好是并查集最擅长的动态连通性场景。用 DFS 每次都重跑就退化成 O(E×(V+E))。

类比失效处 / 易错点

• "地铁图"类比会让人以为边一定有距离。图可以有带权边，也可以无权；可以有权重为负的边（比如"收益"）。
• BFS 找最短路只对无权图成立。带权图必须 Dijkstra。
• 拓扑排序不唯一。多个入度为 0 的节点，出队顺序不同会得到不同结果，都合法。
• Dijkstra 用堆优化后是 O((V+E)log V)，不是 O(E log V)——虽然通常 E 远大于 V，但写法要准确。
• 并查集不能"分裂"。它只支持合并，不支持把集合拆开。需要删除操作要用可持久化并查集或 LCT。

✅ 验收清单

• 能说出邻接矩阵和邻接表各自的适用场景（稠密 vs 稀疏）
• 能默写 BFS 和 DFS 的代码框架，并说出"为什么 BFS 能找到无权图最短路"
• 能用 Kahn 算法写出拓扑排序，并解释"怎么检测环"
• 能说出 Dijkstra / Bellman-Ford / Floyd 各自适用的场景
• 能解释"Dijkstra 为什么不能有负权边"，并给出一个具体反例
• 能写出并查集的 find（含路径压缩）和 union（含按秩合并）
• 能解释"并查集为什么接近 O(1)"，以及它为什么不能处理有向图
• 合上书，用自己的话讲 3 分钟，中途不卡壳