408 知识网络
返回模块节点

DS-4 图

数据结构

来源：10-DS4-图.md · 完整笔记（7 节，未删减）

数据结构模块。逻辑关系的最一般形态“多对多”：交通网、通信网、依赖关系都是图。 图是 DS 中算法最密集的一章：遍历、最小生成树、最短路径、拓扑排序、关键路径五大算法族。

核心问题

这一部分为什么存在？

线性表管“一对一”，树管“一对多”，但现实关系往往是任意的：城市间的公路、路由器的互联、课程间的先修关系。图的主线问题链：

  1. 任意关系怎么存：nn 个顶点的关系最多 n2n^2 种——稠密用矩阵、稀疏用表（存储选择的权衡是一切复杂度分析的前提）；
  2. 怎么不重复不遗漏地访问所有顶点：遍历（DFS/BFS），树遍历的推广——但要自己防环（visited 数组）；
  3. 怎么用最少的边连通所有点：最小生成树（Prim/Kruskal）；
  4. 怎么走最近：最短路径（Dijkstra/Floyd/BFS）；
  5. 事件有先后依赖怎么办：AOV 网的拓扑排序（“能不能排”= 有无环）；
  6. 工程最短多久完工、哪些环节不能拖：AOE 网的关键路径。

概念体系

flowchart TD
    A["多对多的任意关系"] --> B["存储：邻接矩阵（稠密）<br/>vs 邻接表（稀疏）"]
    B --> C["遍历：DFS（栈）/ BFS（队列）<br/>+ visited 防环"]
    C --> D["最小生成树 MST<br/>Prim（选点）/ Kruskal（选边）"]
    C --> E["最短路径<br/>Dijkstra（单源非负）/ Floyd（全源）/ BFS（无权）"]
    A --> F["有向无环图 DAG"]
    F --> G["AOV：拓扑排序<br/>事件先后顺序"]
    F --> H["AOE：关键路径<br/>最长路径 = 最短工期"]

核心概念：

概念 要点 易考点
度/入度/出度 无向图：∑\sum度 =2e= 2e；有向图：∑\sum入度 =∑=\sum出度 =e= e 由邻接矩阵求度：无向图数行（或列）的 1；有向图度 = 行（出）+ 列（入）（2013-7）
连通/强连通 无向连通图至少 n−1n-1 条边；完全图 n(n−1)/2n(n-1)/2 条 2009-7（连通图性质辨析）
邻接矩阵 AmA^m AmA^m 的非零元 (i,j)(i,j) 表示 i 到 j 长度为 m 的路径条数 2015-42 大题直接考
生成树 含全部 nn 顶点、n−1n-1 条边的极小连通子图 MST 代价唯一、形状未必唯一（2012-8、2017-42）
AOV 网 顶点 = 活动，弧 = 先后关系；有环则无拓扑序列 2011-8 III（有拓扑序列 ⟹ 无回路）
AOE 网 顶点 = 事件，边 = 活动（带权）；关键路径 = 源到汇的最长路径 2020-8：缩短任一关键活动不一定缩短工期（有多条关键路径时），经典陷阱

实现机制

1. 存储选择：矩阵还是表

邻接矩阵 邻接表
空间 O(n2)O(n^2)，稠密图合算 O(n+e)O(n+e)，稀疏图合算
判边 (i,j)(i,j) 存在 O(1)O(1) O(O(度))
遍历邻居 O(n)O(n) O(O(度))
BFS/DFS 总复杂度 O(n2)O(n^2) O(n+e)O(n+e)（2012-5）
有向图变体 — 十字链表；无向图：邻接多重表

2. DFS 与 BFS（树遍历的推广）

DFS = 树的先序推广（递归/栈 + visited），BFS = 层序推广（队列 + visited）。考点：序列合法性判断（2013-8：哪个不是 BFS 序列）、可能序列个数（2015-5：从 v0v_0 出发的 DFS 序列数）、DFS 退栈序 = 逆拓扑序列（2020-6：把 visit 移到递归返回前，DAG 上得到逆拓扑有序序列——这是拓扑排序第二种实现的思想）。

3. 最小生成树：Prim 与 Kruskal 的两种贪心

  • Prim（选点）：从任意顶点起，每次把连接树内外的最小权边（及其外端点）并入树，O(n2)O(n^2)，适合稠密图。
  • Kruskal（选边）：边按权升序，逐条并入不成环的边，判环用并查集（DS-3 的应用点），O(elog⁡e)O(e \log e)，适合稀疏图。
  • 考法：选边顺序对比（2015-6：Kruskal 第 2 次选中但 Prim 从 V4V_4 第 2 次不选中的边；2020-7：Kruskal 依次加入的边）；MST 叙述（2012-8：代价唯一 ✓、最小权边必在所有 MST 中 ✗、不同起点 Prim 结果一定相同 ✗）；2017-42 大题（Prim 过程 + MST 唯一的条件：所有边权互不相同则唯一）。

4. 最短路径三兄弟

算法 场景 思想 复杂度 限制
BFS 边权全为 1（或无权） 层数即距离 O(n+e)O(n+e) 仅等权（2023-6）
Dijkstra 单源、权非负 每次确定 dist 最小的点，用它松弛邻居 O(n2)O(n^2)（数组版） 负权失效（贪心依据：已确定点不会再被更新）
Floyd 全源 三重循环：依次允许经过 vkv_k 中转 O(n3)O(n^3) 可负权、不可负环

Dijkstra 的考法固定为“依次得到的最短路径目标顶点顺序”或“某步后 dist 数组内容”（2012-7、2016-8、2021-8）；2009-41 大题给了一个“每次走最近邻”的伪 Dijkstra，要求判断能否求最短路径——不能（贪心只看眼前一步，与 Dijkstra 的“确定 + 松弛”机制不同，举反例即可）。2014-42（OSPF 大题）正是 Dijkstra 在计网路由中的真实应用——X-8 连接点。

5. 拓扑排序与关键路径

  • 拓扑排序（AOV）：反复“选入度为 0 的顶点输出并从图中删去其出边”；O(n+e)O(n+e)（2016-7）。排不出来 ⟺ 有环。考法：序列个数（2010-8、2021-7）、合法性（2014-7、2018-7）、与 DFS 的关系（2020-6）。
  • 关键路径（AOE）：先正推事件最早发生时间 veve（取最大），再逆推最晚 vlvl（取最小），活动余量 = vl[终点]−ve[起点]−权vl[\text{终点}] - ve[\text{起点}] - \text{权}，余量 0 的活动即关键活动，串成关键路径。关键路径 = 最长路径（决定工期上限）；2020-8 陷阱：缩短一条关键路径上的活动，若存在另一条并列关键路径则工期不变。2011-41 大题（上三角邻接矩阵存的一维数组 → 还原矩阵 → 求关键路径及长度）。

方案比较

Prim vs Kruskal（本模块第一易混对）：为什么易混——都求 MST、都是贪心。本质区别——Prim 以顶点为生长点（树一团越长越大，看“树到非树”的边），Kruskal 以边为主线（全图择优，用并查集防环）。判别线索：稠密图/给邻接矩阵 → Prim 顺手；稀疏图/给边列表 → Kruskal 顺手；问“第 k 次选中的边”→ 分别按各自规则模拟。

Dijkstra vs Floyd：为什么易混——都求最短路径。本质区别——单源 vs 全源、贪心确定 vs 动态规划中转。判别线索：题目问“从某点到各点”→ Dijkstra；“任意两点间”→ Floyd；“权都是 1”→ BFS 最快。

DFS vs BFS（遍历对）：DFS 走得深（栈），适合“路径存在性、拓扑、连通分量计数”；BFS 走得匀（队列），适合“无权最短路、层数”。

应用与考法

形态一：存储与概念：2013-7（矩阵求度）、2011-8（存储与拓扑叙述）、2015-42（AmA^m 非零元含义）、2009-7。

形态二：遍历：2012-5（邻接表 BFS O(n+e)O(n+e)）、2013-8、2015-5、2020-6（逆拓扑）、2023-6（无权最短路用 BFS）。

形态三：MST：2012-8、2015-6、2017-42（大题）、2020-7。

形态四：最短路径：2009-41（大题：贪心反例）、2012-7、2016-8、2021-8。

形态五：拓扑与关键路径：2010-8、2014-7、2016-7、2018-7、2021-7、2011-41（大题）、2020-8。

形态六（与 DS-7 衔接）：图类代码大题：2021-41（邻接矩阵上判 EL 路径存在性 = 统计奇度顶点个数）、2023-41（邻接矩阵上找出度 > 入度的 K 顶点）——图类代码题近年风格是“遍历 + 度/性质统计”，模板见 DS-7。

做题触发词：看到“邻接矩阵”+ 遍历 → O(n2)O(n^2)；看到“依次得到最短路径”→ Dijkstra 逐步模拟；看到“第 2 次选中的边”→ Prim/Kruskal 分开模拟；看到“排课/先后依赖”→ 拓扑排序；看到“工期/最长”→ 关键路径。

来源：真题markdown/2009-2024统考真题.md 对应题号。

前后联系

  • 向前依赖：DS-2（栈/队列支撑 DFS/BFS）、DS-3（树是图的特例；并查集支撑 Kruskal；哈夫曼合并与 Prim 都是贪心）。
  • 向后引出：
    • 图论建模渗透 DS-5/DS-6（比较次数判定树、排序网络，理解级）；
    • 跨学科：Dijkstra = OSPF（CN-3，2014-42）、距离向量 ≈ 分布式 Bellman-Ford（RIP）；网络拓扑即图（CN-6）；进程资源分配图（OS-4 死锁检测）；DAG → OS 进程前驱关系（PV 前驱图模板，OS-3）——X-8。

闭卷回忆链

  1. 为什么树不够用？（多对多 → 图；树是无环连通图）
  2. 稠密图和稀疏图各怎么存？BFS 在两种存储下的复杂度？
  3. 遍历为什么要 visited 数组？DFS 和 BFS 各靠什么结构？
  4. 怎么用最少的边连通所有点？Prim 和 Kruskal 的贪心对象各是什么？
  5. Kruskal 怎么判环？（并查集）
  6. MST 的代价和形状都唯一吗？什么条件下形状唯一？
  7. 单源最短路径为什么 Dijkstra 要求非负权？（贪心确定后不能再被更新）
  8. “每次走最近邻”为什么不是 Dijkstra？（无松弛机制，2009-41 反例）
  9. 权全为 1 时谁最快？任意两点间谁来做？（BFS / Floyd）
  10. 有向图怎么判断能否拓扑排序？算法怎么做？（入度 0 队列）
  11. 关键路径为什么是最长路径？缩短关键活动一定能缩工期吗？
  12. 图论如何接入计网路由与 OS 死锁？（Dijkstra=OSPF；资源分配图判环——X-8）