考研复习 Day 19 | 数据结构与算法--图（下）
一、最小生成树（MST）
最小生成树：带权连通无向图中，总权重最小的生成树。
1.1 MST的性质
| 性质 | 说明 |
|---|---|
| 不唯一性 | 若图中有权值相同的边，MST可能不唯一；若所有边权值互不相同，则MST唯一 |
| 总权重唯一 | 所有MST的总权重相同，且为最小值 |
| 边数固定 | MST的边数 = 顶点数 - 1 |
| 注意 | MST中任意两点间的路径不一定是最短路径 |
1.2 Prim算法
核心思想：从某个顶点开始，每次选择与当前树距离最近的顶点加入。
步骤：
任取一个顶点加入树T
选择与T中顶点距离最近的顶点及其最小权值边加入T
重复直到所有顶点都在T中
时间复杂度：O(n²)（与边数无关，适合稠密图）
1.3 Kruskal算法
核心思想：按边权值递增顺序，每次选择不形成回路的边加入。
步骤：
初始时每个顶点自成一个连通分量
按权值从小到大考察每条边
若边连接两个不同连通分量，则加入（用并查集判断）
重复直到有n-1条边
时间复杂度：O(|E| log₂|E|)（适合稀疏图）
二、最短路径
2.1 Dijkstra算法（单源最短路径）
核心思想：贪心策略，每次选择当前距离最短的顶点加入集合S。
辅助数组：
final[]：标记顶点是否已确定最短路径dist[]：从源点到各顶点的当前最短路径长度path[]：记录路径前驱，用于回溯
步骤：
初始化：S={源点}，dist[i]=arcs[源点][i]
从V-S中选dist最小的顶点j加入S
松弛操作：若dist[j]+arcs[j][k] < dist[k]，则更新dist[k]
重复n-1次
时间复杂度：O(n²)（邻接矩阵）/ O(n²)（邻接表+线性扫描）
注：Dijkstra算法不适用于存在负权边的图
2.2 Floyd算法（各顶点之间最短路径）
核心思想：动态规划，逐步允许更多顶点作为中间顶点。
递推公式：
A⁽ᵏ⁾[ i ] [ j ] = min(A⁽ᵏ⁻¹⁾[ i ] [ j ], A⁽ᵏ⁻¹⁾[ i ] [ k ] + A⁽ᵏ⁻¹⁾[ k ] [ j ])
初始：A⁽⁻¹⁾[ i ] [ j ] = arcs[ i ] [ j ]
最终：A⁽ⁿ⁻¹⁾[ i ] [ j ] 为i到j的最短路径长度
时间复杂度：O(n³)
注：Floyd算法允许负权边，但不允许负权回路
2.3 三种最短路径算法对比
| 算法 | 用途 | 适用图 | 时间复杂度 |
|---|---|---|---|
| BFS | 单源 | 无权图 | O(n+|E|) |
| Dijkstra | 单源 | 带权图（无负权） | O(n²) |
| Floyd | 所有顶点对 | 带权图（无负权回路） | O(n³) |
三、有向无环图（DAG）描述表达式
DAG：不含任何有向环路的有向图。
应用：表示含有公共子表达式的代数表达式，公共子表达式只存储一次，通过多个父结点共享，节省存储空间。
四、拓扑排序
AOV网：顶点表示活动，有向边
<vᵢ, vⱼ>表示活动vᵢ必须先于vⱼ进行。
拓扑排序：将AOV网中所有顶点排成一个线性序列，满足：
每个顶点恰好出现一次
若存在从A到B的路径，则A排在B之前
拓扑排序算法：
选择入度为0的顶点输出
删除该顶点及其所有出边
重复直到没有顶点（成功）或找不到入度为0的顶点（有环）
逆拓扑排序：选择出度为0的顶点输出
时间复杂度：邻接表 O(n+|E|)；邻接矩阵 O(n²)
DFS实现拓扑排序：按DFS结束时间降序排列
拓扑排序的唯一性条件：每次输出时入度为0的顶点只有一个
五、关键路径
AOE网：顶点表示事件，边表示活动，边上的权值表示活动持续时间。
| 术语 | 定义 |
|---|---|
| 源点 | 入度为0的顶点，工程起点（唯一） |
| 汇点 | 出度为0的顶点，工程终点（唯一） |
| 关键路径 | 从源点到汇点路径长度最大的路径 |
| 关键活动 | 关键路径上的活动 |
关键参数：
| 参数 | 含义 | 计算公式 |
|---|---|---|
| ve(k) | 事件k的最早发生时间 | 拓扑顺序递推：ve(k)=max{ve(j)+Weight(j,k)} |
| vl(k) | 事件k的最迟发生时间 | 逆拓扑顺序递推：vl(k)=min{vl(j)-Weight(k,j)} |
| e(i) | 活动aᵢ的最早开始时间 | e(i)=ve(起点) |
| l(i) | 活动aᵢ的最迟开始时间 | l(i)=vl(终点)-Weight |
| d(i) | 活动aᵢ的时间余量 | d(i)=l(i)-e(i) |
关键活动：
d(i)=0的活动
求关键路径的步骤：
拓扑顺序求 ve ()
逆拓扑顺序求 vl ()
计算所有活动的 e () 和 l ()
找出 d () = 0 的活动构成关键路径
关键路径的性质：
| 性质 | 说明 |
|---|---|
| 关键路径长度 | 工程的最短完成时间 |
| 加快关键活动 | 可能缩短工期，但过度缩短会导致关键路径转移 |
| 多条关键路径 | 需加快所有关键路径上的公共关键活动才能缩短工期 |
六、思考
1. Prim算法 ≈ 社交圈的扩展
例如你有一个朋友圈，每次加入一个离这个圈子最近的新朋友，直到所有人都加入。这就是Prim。
2. Kruskal算法 ≈ 相亲节目配对
按心动值从小到大考虑，如果两个人不在同一对（不形成回路），就配对，直到所有人都配对成功。
3. Dijkstra算法 ≈ 外卖骑手规划
从起点出发，每次选当前能最快到达的未送餐点，然后更新其他点的最快时间。不能有负权（不能有“倒贴钱”的路线）。
4. 拓扑排序 ≈ 课程安排
学数据结构之前要先学C语言，学算法之前要先学数据结构。按依赖关系排课，就是拓扑排序。
5. 关键路径 ≈ 工程赶工期
项目的总工期由最长的依赖链决定。想提前完工，必须压缩这条链上的关键任务。
七、附录：各种图算法时间复杂度汇总
| 算法 | 邻接矩阵 | 邻接表 |
|---|---|---|
| Prim | O(n²) | — |
| Kruskal | — | O( |E|log₂|E| ) |
| Dijkstra | O(n²) | O(n²) |
| Floyd | O(n³) | — |
| BFS/DFS | O(n²) | O(n+|E|) |
| 拓扑排序 | O(n²) | O(n+|E|) |
| 关键路径 | O(n²) | O(n+|E|) |
注：以上内容参考 2027年数据结构考研复习指导 王道论坛 组编，其中有一些个人想法，如有任何错误或不妥，欢迎各位大佬指出，如果各位有一些有意思的想法，也可以和我交流一下~感谢！
八、明日计划
查找算法