数据结构第 6 章：图——存储、遍历、最小生成树与最短路径

图是全课程最难也最有价值的一章。它把前五章的东西全用上了：邻接表用链表，DFS 用栈/递归，BFS 用队列，最小生成树用贪心（第 3 章之后的算法设计思想在这里第一次出现）。这一章学通了，第 7、8 章和第 9 章算法设计会轻松很多；跳过它，考研和面试都会在这一块失分。

一、术语（讲不清术语就没法做题）

• 有向图 / 无向图：边是否有方向。无向图里 (vᵢ,vⱼ) 无序，有向图里 有序
• 度：无向图中顶点的度是与它关联的边数，所有顶点度数之和 = 2e；有向图分入度、出度，入度之和 = 出度之和 = e
• 路径、回路（环）：简单路径要求顶点不重复
• 连通图：无向图中任意两顶点都有路径。连通图的生成树含 n 个顶点、恰好 n−1 条边
• 连通分量：无向图的极大连通子图；有向图对应强连通分量
• 网：带权图

二、两种存储结构：选哪个决定了后面所有算法的复杂度

邻接矩阵：n×n 的二维数组，A[i][j] = 1（或权值）表示有边。空间 O(n²)，与边数无关；判断两点是否相邻 O(1)；求某顶点所有邻接点要扫一整行 O(n)。适合稠密图。

无向图的邻接矩阵对称，可压缩存三角；有向图不对称。

邻接表：每个顶点挂一条单链表，存它的所有邻接点。空间 O(n+e)；判断两点是否相邻要扫链表；求某顶点所有邻接点很快。适合稀疏图。

有向图用邻接表时，求出度容易、求入度难（要遍历全部链表），所以有的场景要逆邻接表；两者都要时用十字链表。无向图需要同时找一条边的两个端点时用邻接多重表。

一句话：稠密图用矩阵，稀疏图用邻接表。这个选择直接决定了遍历算法的复杂度表达式。

三、遍历：DFS 和 BFS 只差一个数据结构

深度优先（DFS）：一条路走到黑，走不通再回退。用递归或栈实现。类似树的先序遍历。

广度优先（BFS）：先访问所有邻接点，再一层层往外扩。用队列实现。类似树的层序遍历。

复杂度（关键，考试必考）：

存储方式	DFS	BFS
邻接矩阵	O(n²)	O(n²)
邻接表	O(n+e)	O(n+e)

空间：DFS 递归深度最坏 O(n)，BFS 队列最坏 O(n)。

应用差异：BFS 能求无权图的最短路径（第一次到达某点时的层数就是最少边数）；DFS 适合判连通性、求连通分量、拓扑排序、找环。同一个图从不同顶点出发，遍历序列可能不同——遍历序列不唯一是常见考点。

四、最小生成树：Prim 与 Kruskal

生成树要求连通所有 n 个顶点、只有 n−1 条边、无环。最小生成树（MST）是边权之和最小的生成树。

Prim（加点法）：从一个顶点出发，每次选"连接已选集合与未选集合的最小边"的那个顶点加入。复杂度 O(n²)（与边数无关）→ 适合稠密图。

Kruskal（加边法）：把所有边按权值排序，从小到大选边，加入后不成环就保留，直到选够 n−1 条。复杂度 O(e log e) → 适合稀疏图。

两者都是贪心。Kruskal 判环用并查集。注意：MST 可能不唯一（等权边存在时），但 MST 的总权值唯一。

五、最短路径：Dijkstra 与 Floyd

Dijkstra（单源）：求某个源点到其余所有顶点的最短路径。用贪心 + 逐步确定，每次选当前距离最小的未确定顶点加入。复杂度 O(n²)，用堆优化可到 O((n+e) log n)。

★ Dijkstra 不能处理负权边——它的正确性建立在"已确定的点距离不会再变小"这个前提上，负权会破坏这个前提。这是最常考的陷阱。

Floyd（多源）：求任意两点间的最短路径。三重循环，复杂度 O(n³)，空间 O(n²)。思想是动态规划：D[i][j] = min(D[i][j], D[i][k] + D[k][j])，k 那一层必须放在最外层。

Floyd 可以处理负权（但不能有负权环）。

六、拓扑排序与关键路径

AOV 网：用顶点表示活动、边表示活动之间的先后关系（有向无环图 DAG）。

拓扑排序：把 AOV 网排成一个线性序列，使所有前驱都在后继之前。做法反复"选一个入度为 0 的顶点输出，然后删掉它的出边，更新入度"。复杂度 O(n+e)。

如果拓扑排序输出的顶点数少于 n，说明图中有环 ——这是判断有向图是否有环的标准方法，实际工程里用来检测循环依赖（构建系统、包管理器都用它）。

AOE 网：用边表示活动、权值表示活动持续时间，求整个工程的最短工期。需要算四个量：事件最早发生时间 ve、最迟发生时间 vl、活动最早开始 e、最迟开始 l。l == e 的活动是关键活动，关键活动构成的路径就是关键路径（可以有多个）。缩短工期只能压缩关键活动。

易错点与做题顺序建议

1. 先能把一个图正确地写出邻接矩阵和邻接表（这是所有题的第一步）
2. 再手推 DFS/BFS 序列（注意顶点访问顺序按编号或按表顺序，题目会说明）
3. 然后按"稠密/稀疏"选 MST 算法，按"单源/多源"选最短路算法
4. 最后练拓扑排序与关键路径的手工计算

算法选择题的判断口诀：看到"负权"就排除 Dijkstra；看到"任意两点"用 Floyd；看到"稠密图最小生成树"用 Prim；看到"稀疏图最小生成树"用 Kruskal。

这一章在整门课里的位置

本章把前面所有工具都用了一遍：邻接表用第 2 章的链表，DFS 用第 3 章的递归/栈，BFS 用第 3 章的队列，最小生成树与最短路径是第 9 章贪心策略的实例。往后看，第 7、8 章的排序与查找处理的是线性结构，而真实工程里的数据多是图结构——第 6 章是从"数据结构"走向"算法设计"的转折点。

本篇是《数据结构与算法（93 讲）》第 6 章的知识点摘要。所有算法都有 C 语言实现与手工推演演示，见 课程页；上一章 树与二叉树，下一章 排序。