> For the complete documentation index, see [llms.txt](https://datastructure-1.gitbook.io/datastructure-docs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://datastructure-1.gitbook.io/datastructure-docs/di-wu-bu-fen-tu/11-graph-algorithms.md). # 第 11 章：图论算法 [<- 第 10 章　多维搜索树（KD 树）](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/10-kd-tree.md) | [课程目录](/datastructure-docs/readme.md) | [第 12 章　哈希表 ->](/datastructure-docs/di-liu-bu-fen-cha-zhao/12-hash-tables.md) > 所属模块：第五部分：图\ > 对应实现：graph.cpp ### 本章导航 * [11.1 图论基础：从树到多对多网络](#c11-11-1) * [11.2 图的三大经典存储范式：矩阵、邻接表与链式前向星](#c11-11-2) * [11.3 深度与广度优先遍历（DFS vs BFS）及四类边拓扑剖析](#c11-11-3) * [11.4 拓扑排序（Topological Sort）：DAG 的线性化调度](#c11-11-4) * [11.5 最小生成树（MST）：切割定理与 Prim vs Kruskal](#c11-11-5) * [11.6 最短路径四大算法全家桶与松弛技术](#c11-11-6) * [11.6.1 Dijkstra 算法：贪心正确性与非负权限制剖析](#c11-11-6-1) * [11.6.2 Bellman-Ford 与 SPFA：负权边支持与负环检测](#c11-11-6-2) * [11.6.3 Floyd-Warshall：动态规划求全源最短路](#c11-11-6-3) * [11.7 工程项目管理之魂：AOE 网与关键路径（CPM）大题手算演练](#c11-11-7) * [11.8 图算法工程技术选型雷达](#c11-11-8) * [本章小结](#c11-summary) * [思考题与经典大厂面试题](#c11-exercises) *** ## 第 11 章　图论算法 > 难度：★★★★★ | 代码：[graph.cpp](https://github.com/Huo0077/DataStructure/blob/main/graph.cpp) **前置知识**：[第 3 章](/datastructure-docs/di-er-bu-fen-xian-xing-jie-gou/03-stacks-and-queues.md) 队列（BFS）与栈（DFS），[第 7 章](/datastructure-docs/di-si-bu-fen-shu-yu-er-cha-shu/07-heap-and-priority-queue.md) 堆（Dijkstra / Prim 优先队列优化），[第 13 章](/datastructure-docs/di-liu-bu-fen-cha-zhao/13-disjoint-set-union.md) 并查集（Kruskal 环检测）。 **学习目标**： 1. 掌握邻接矩阵、邻接表以及高性能“链式前向星”的内存布局与访问开销； 2. 掌握 DFS 树中四类边（树边、回边、前向边、横叉边）的有向图拓扑含义与环检测； 3. 深刻理解贪心切割定理（Cut Property）在最小生成树中的指导作用； 4. 透彻理解 Dijkstra 贪心松弛界，掌握负权边导致其失效的底层原因； 5. 熟练掌握 AOE 网关键路径中 `etv`, `ltv`, `ete`, `lte` 四大数组的手算推导。 *** ### 11.1 图论基础：从树到多对多网络 如果说树是“层级分明、无环连接”的特殊图（(n) 个节点恰好 (n-1) 条边），那么**图（Graph, (G = (V, E))）** 则是表达客观世界实体间“多对多”复杂关系的通用数学语言。 * **顶点集（Vertex Set, (V)）**：实体的集合，(|V| = n)； * **边集（Edge Set, (E)）**：关系的集合，(|E| = m)； * **有向图 vs 无向图**：边是否存在方向性； * **权（Weight）**：边上的标量值（距离、费用、时延、容量）； * **简单路径 vs 环（Cycle）**：顶点不重复出现的路径称为简单路径；起点终点重合且边数 (\ge 3) 的简单路径构成环。 *** ### 11.2 图的三大经典存储范式：矩阵、邻接表与链式前向星 选择何种数据结构存储图，直接决定了图算法的常数因子与渐进复杂度： ``` 【1. 邻接矩阵 (Adjacency Matrix)】 【2. 邻接表 (Adjacency List)】 空间: O(V²) 空间: O(V + E) 判两点相邻: O(1) 判两点相邻: O(degree(u)) 遍历某点所有出边: O(V) 遍历某点所有出边: O(degree(u)) 适用: 稠密图 (E ≈ V²) 适用: 稀疏图 (E << V²) 0 1 2 3 0 ───> [ 1, w=5 ] ───> [ 2, w=2 ] 0 [0, 5, 2, 0] 1 ───> [ 3, w=1 ] 1 [0, 0, 0, 1] 2 ───> [ 3, w=6 ] 2 [0, 0, 0, 6] 3 ───> nullptr 3 [0, 0, 0, 0] ``` #### 3. 高性能存储王牌：链式前向星（Forward Star） 在算法竞赛和追求极限性能的工业引擎中，`std::vector adj[V]` 的频繁小对象分配会产生严重的缓存未命中（Cache Miss）。**链式前向星**利用三个扁平的一维静态数组，实现了对邻接表的零指针、缓存紧凑化压缩： ```cpp const int MAXV = 10000; const int MAXE = 100000; int head[MAXV]; // head[u] 存储顶点 u 的第一条出边在 edges 数组中的下标 int to[MAXE]; // to[e] 存储第 e 条边的终点 int weight[MAXE]; int nxt[MAXE]; // nxt[e] 存储与第 e 条边同起点的下一条边下标 int edgeCount = 0; void addEdge(int u, int v, int w) { to[edgeCount] = v; weight[edgeCount] = w; nxt[edgeCount] = head[u]; // 头插法串联同起点的边 head[u] = edgeCount++; } // 遍历顶点 u 的所有出边：极其迅速！ for (int e = head[u]; e != -1; e = nxt[e]) { int v = to[e]; int w = weight[e]; // 处理邻接点 v } ``` *** ### 11.3 深度与广度优先遍历（DFS vs BFS）及四类边拓扑剖析 | 算法 | 核心数据结构 | 空间复杂度 | 核心特性 | 经典适用场景 | | ------------- | ----------- | -------------- | ----------------- | ----------------------------- | | **BFS（广度优先）** | 队列（Queue） | (O(V))（最宽层节点数） | 逐层扩散，具有**最短步数保证** | 无权图单源最短路径、连通块染色、二分图判定 | | **DFS（深度优先）** | 递归调用栈 / 显式栈 | (O(V))（最深递归深度） | 一路深入到底，撞墙回溯 | 连通性分析、拓扑排序、强连通分量（Tarjan）、回溯搜索 | #### DFS 生成森林中的四类边（有向图深层拓扑）： 当对有向图运行 DFS 时，每个顶点被打上两个时间戳：发现时间 `d[u]` 和完成时间 `f[u]`。此时图中的每条边 ((u, v)) 被严格归入四类之一： ``` 1. 树边 (Tree Edge): DFS 搜索树的实际分支边，直接通往未访问的白色节点。 2. 回边 (Back Edge): 由子孙节点指向 DFS 树中的祖先节点 ───> 【存在回边 ⟺ 图中必有有向环！】 3. 前向边 (Forward Edge):由祖先节点直接指向非直接后代的树下部节点。 4. 横叉边 (Cross Edge): 连接两个互无祖先关系的平行分支，或跨越不同连通分量。 ``` > **无向图的重要定理**：在无向图的 DFS 生成树中，**绝不会出现前向边和横叉边**，所有的边非此即彼，要么是树边，要么是回边！ *** ### 11.4 拓扑排序（Topological Sort）：DAG 的线性化调度 **有向无环图（Directed Acyclic Graph, DAG）** 是任务依赖调度的通用数学模型（例如：大学课程选修依赖、Makefile 编译依赖、任务流调度）。\ **拓扑排序**：将 DAG 中所有顶点排成一个线性序列，使得对于任意边 (u \to v)，(u) 在序列中必须排在 (v) 的前面。 #### Kahn 算法（基于入度的 BFS 队列法）： 1. 统计每个顶点的入度（`in_degree`）； 2. 将所有入度为 0 的顶点压入队列（入度为 0 意味着无前置依赖，可立即执行）； 3. 当队列非空时： * 弹出队头 (u)，加入拓扑序列； * 遍历 (u) 的所有邻接出边 (u \to v)，令 (v) 的入度减 1（`--in_degree[v]`）； * 若 (v) 的入度衰减为 0，将其压入队列； 4. **判环不变量**：若最终拓扑序列中的顶点数 (< |V|)，说明**图中存在有向环，拓扑排序不存在！** *** ### 11.5 最小生成树（MST）：切割定理与 Prim vs Kruskal **问题**：给定连通无向带权图 (G = (V, E))，选出 (V - 1) 条边，在保证图依然连通的前提下，使得选出的边权之和最小。 #### 贪心选择的数学基石：切割定理（Cut Property） * 将顶点集 (V) 任意划分为两个互不相交的子集 (S) 和 (V - S)，连接这两个集合的所有边构成的集合称为一个**割（Cut）**； * **切割定理**：跨越该割的所有边中，**权值最小的那条边（轻边，Light Edge）必然属于某棵最小生成树**！ ``` 【Prim 算法 (加点法)】 【Kruskal 算法 (加边法)】 - 思想: 维护一个不断长大的树点集 S - 思想: 全局边权升序排序，贪心选边 - 策略: 每次寻找跨越 S 与 V-S 的最短边 - 策略: 用并查集判环，若两端不在同一连通块则加入 - 复杂度: O(E log V) (堆优化) - 复杂度: O(E log E) - 最佳战场: 稠密图 (E ≈ V²) - 最佳战场: 稀疏图 (E << V²) ``` *** ### 11.6 最短路径四大算法全家桶与松弛技术 **松弛操作（Relaxation）** 是所有最短路径算法的共同原子操作： ```cpp void relax(int u, int v, int weight) { if (dist[v] > dist[u] + weight) { dist[v] = dist[u] + weight; // 经由 u 走向 v 能够缩短总路程 } } ``` #### 11.6.1 Dijkstra 算法：贪心正确性与非负权限制剖析 Dijkstra 算法维护一个已经确定最短距离的集合 (S)： 1. 初始令 `dist[src] = 0`，其余置为 (\infty)； 2. 每次从未确定集合 (V - S) 中选取当前 `dist` 最小的顶点 (u) 加入 (S)（利用小顶堆优化为 (O(\log V))）； 3. 用 (u) 的所有出边对邻接点进行松弛； 4. 重复步骤 2 和 3 直到所有顶点都被处理。 ``` 【为什么 Dijkstra 面对负权边必然崩溃？】 考虑网络: A ──(5)──> B, A ──(1)──> C ──(-10)──> B 第 1 轮: 从 A 出发，dist[B]=5, dist[C]=1 第 2 轮: 贪心地选取未锁定的最小者 C (dist=1) 锁定! 松弛 C->B: dist[B] = min(5, 1 + (-10)) = -9 第 3 轮: 锁定 B (dist=-9) 看似正常？但如果网络是: A ──(2)──> B ──(1)──> C │ ▲ └────────(-5)─────────┘ Dijkstra 在第 1 轮会把 B 锁定为 2（因为 2 < 无穷大），随后 C 被松弛为 3。 但实际存在 A 直接向 C 走 -5 的捷径！一旦节点被出堆锁定，Dijkstra 永不复查，彻底失误！ ``` #### 11.6.2 Bellman-Ford 与 SPFA：负权边支持与负环检测 * **核心逻辑**：对图中的全部 (E) 条边执行整整 (V - 1) 轮松弛循环。 * **为什么是 (V - 1) 轮？**\ 在一个不含负环的图中，任何单源最短简单路径至多包含 (V - 1) 条边。第 (k) 轮松弛保证了所有至多包含 (k) 条边的最短路径均被正确求出。 * **负环检测**：若在第 (V) 轮松弛中，依然有边能够被成功松弛，**说明图中必然存在权值和为负数的环路（Negative Cycle）！** 因为只有负环才能无限次缩短距离！ * **SPFA 算法**：利用队列仅将“上一轮 `dist` 发生减小的节点”入队去松弛邻居。平均复杂度 (O(kE))，但面对网格图等最坏数据会退化为 (O(VE))。 #### 11.6.3 Floyd-Warshall：动态规划求全源最短路 求任意两点 (i) 到 (j) 的最短路径。 * **状态定义**：(dp\[k]\[i]\[j]) 表示只允许经过前 (k) 个顶点作为中间过渡节点时，从 (i) 到 (j) 的最短路径。 * **状态转移方程**： \[ dp\[k]\[i]\[j] = \min(dp\[k-1]\[i]\[j], dp\[k-1]\[i]\[k] + dp\[k-1]\[k]\[j]) ] * **空间压缩**：由于 (dp\[k]) 仅依赖 (dp\[k-1])，最外层 (k) 的维度可以直接抹去： ```cpp for (int k = 0; k < V; ++k) { for (int i = 0; i < V; ++i) { for (int j = 0; j < V; ++j) { if (dist[i][k] != INF && dist[k][j] != INF) { dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]); } } } } ``` > ⚠️ **最外层循环必须是 (k)**！若把 (k) 放在内层，动态规划的无后效性将被彻底打破！ *** ### 11.7 工程项目管理之魂：AOE 网与关键路径（CPM）大题手算演练 在现代软件工程、建筑工程与芯片设计中，**关键路径法（Critical Path Method, CPM）** 是计算总工期和确定瓶颈工序的核心工具。 * **AOE 网（Activity On Edge Network）**： * **顶点**表示**事件（Event）**（某阶段完成的里程碑时刻）； * **有向边**表示**活动（Activity）**，边权表示持续时间。 * **四大关键数组（考研与大厂手算标准）**： 1. `etv[k]`（Earliest Time of Vertex）：事件 (k) 的**最早发生时间**； 2. `ltv[k]`（Latest Time of Vertex）：事件 (k) 的**最晚允许发生时间**； 3. `ete[r]`（Earliest Time of Edge）：活动 (a\_r = \langle u, v \rangle) 的**最早开始时间**（(ete\[r] = etv\[u])）； 4. `lte[r]`（Latest Time of Edge）：活动 (a\_r = \langle u, v \rangle) 的**最晚允许开始时间**（(lte\[r] = ltv\[v] - \text{weight})）。 * **关键活动**：满足 `lte[r] - ete[r] == 0`（即松弛时间 / 时差为 0）的活动！所有关键活动串联起来的路径即为**关键路径（工期瓶颈）**！ #### 完整手算追踪示例： ``` [v2] ───(a4=1)───> [v5] ▲ \ ▲ \ (a1=3) (a3=2) (a5=3) (a8=1) / v / v [v1] ───(a2=2)───> [v3] ───(a7=2)───> [v6] \ ▲ (a6=4) / v / [v4] ─┘ ``` 1. **正向拓扑推进求 `etv`（取各前驱的最大值）**： * `etv[v1] = 0` * `etv[v2] = etv[v1] + 3 = 3` * `etv[v4] = etv[v1] + 4 = 4` * `etv[v3] = max(etv[v1]+2, etv[v2]+2, etv[v4]+0) = max(2, 5, 4) = 5` * `etv[v5] = max(etv[v2]+1, etv[v3]+3) = max(4, 8) = 8` * `etv[v6] = max(etv[v5]+1, etv[v3]+2) = max(9, 7) = 9` $\implies$ **全工程总工期为 9！** 2. **逆向拓扑倒推求 `ltv`（取各后继的最小值）**： * `ltv[v6] = 9` * `ltv[v5] = ltv[v6] - 1 = 8` * `ltv[v3] = min(ltv[v5] - 3, ltv[v6] - 2) = min(5, 7) = 5` * `ltv[v2] = min(ltv[v5] - 1, ltv[v3] - 2) = min(7, 3) = 3` * `ltv[v1] = min(ltv[v2]-3, ltv[v3]-2, ltv[v4]-4) = 0` 3. **活动时差判定**： * 活动 (a\_1 = \langle v1, v2 \rangle)：`ete = 0`, `lte = 3 - 3 = 0` $\implies$ **关键活动！** * 活动 (a\_3 = \langle v2, v3 \rangle)：`ete = 3`, `lte = 5 - 2 = 3` $\implies$ **关键活动！** * 活动 (a\_5 = \langle v3, v5 \rangle)：`ete = 5`, `lte = 8 - 3 = 5` $\implies$ **关键活动！** * 活动 (a\_8 = \langle v5, v6 \rangle)：`ete = 8`, `lte = 9 - 1 = 8` $\implies$ **关键活动！** * **关键路径为：(v1 \to v2 \to v3 \to v5 \to v6)**！ *** ### 11.8 图算法工程技术选型雷达 ``` 【图算法选型决策树】 │ ┌─────────────────────────────────┼─────────────────────────────────┐ ▼ ▼ ▼ 【连通性与拓扑】 【最小生成树 (MST)】 【最短路径问题】 ├─ 无向图连通块: BFS / 并查集 ├─ 稀疏图: Kruskal (并查集) ├─ 无权图: BFS ├─ 有向图拓扑序: Kahn (入度队列) └─ 稠密图: Prim (堆优化) ├─ 单源非负权: Dijkstra (小顶堆) └─ 有向图强连通分量: Tarjan 算法 ├─ 单源含负权: Bellman-Ford / SPFA ├─ 全源最短路: Floyd-Warshall (O(V³)) └─ 工程项目工期: AOE 关键路径 ``` *** ### 本章小结 1. **链式前向星是性能利器**：以一维数组模拟邻接链表，最大化 CPU 缓存命中率。 2. **生成树与回边**：DFS 生成树不仅是搜索路径，回边的存在是有向图判环的充要条件。 3. **松弛操作统领最短路**：Dijkstra 用贪心锁死非负权，Bellman-Ford 用 (V-1) 轮全覆盖化解负权，Floyd 以外层阶段 (k) 贯通全源。 4. **关键路径是时差的消解**：最早与最迟时间的碰撞锁定了工程进度的绝对瓶颈。 *** ### 思考题与经典大厂面试题 1. **差分约束系统（Difference Constraints）**：给定一组不等式 (x\_i - x\_j \le c\_k)，如何将其转化为有向图的最短路径问题？系统无解对应于图论中的什么特征？ 2. **关键路径的唯一性与优化**：一个 AOE 网中是否存在多条关键路径？若想缩短整个项目的总工期，仅仅压缩某一条关键路径上的某一个活动是否一定奏效？ 3. **二分图的最大匹配（Bipartite Matching）**：如何将二分图的最大匹配问题转化为网络流（Network Flow）的最大流问题？