主题
字号
CHAPTER 04 ≈ 35 MIN READ

图

4.1 为什么需要图：表达「多对多」的复杂关系

线性结构是 1 对 1（一条队），树是 1 对多（一个爹多个娃），但现实里大量关系是多对多——任意两个事物都可能有联系。城市之间的航线（每个城市都通往多个城市）、社交网络的好友关系、网页之间的超链接、地图上的道路、任务之间的依赖……这些都不是「队」也不是「树」，而是网。图（Graph） 就是描述这种「多对多」关系的数据结构，是这门课第二大重头（仅次于树），也是最贴近真实复杂问题的结构。

图比树复杂在哪？树有明确的「根」和「方向」（从上往下），无环、有层次；而图可能任意两点相连、可能有环、可能没有起点、可能不连通。所以图的算法（怎么不重复地走遍、怎么找最短路、怎么排先后）都要更小心，这也是它考点密集的原因。

4.2 基本概念与术语（密集，逐个攻克）

图 G = (V, E)：V 是顶点（Vertex）的集合，E 是边（Edge）的集合。边表示两个顶点之间的关系。

4.2.1 有向 vs 无向

4.2.2 度

4.2.3 完全图、稠密图、稀疏图

4.2.4 路径、连通、环

4.2.5 带权图（网）

边上带有数值（叫权值 weight，可表示距离、费用、时间等）的图叫网。最小生成树、最短路径都是在网上做的。

4.2.6 生成树

一个连通图的生成树，是包含图中全部 n 个顶点、但只用 n−1 条边且不成环的极小连通子图。换句话说，生成树是「用最少的边把所有顶点连起来」。一个图可以有多棵生成树。带权图里权值之和最小的生成树，就是最小生成树（MST）（6.5 节）。

术语很多，但都不难。建议自己画两个图（一个无向、一个有向带权），把每个术语在图上指认一遍。读不懂题往往是术语没过关。

4.3 图的存储结构（必考对比：邻接矩阵 vs 邻接表）

图怎么存进计算机？两大主流方法，它俩的对比是必考点。

4.3.1 邻接矩阵（适合稠密图）

用一个 n×n 的二维数组 A 表示。A[i][j] 记录顶点 i 和顶点 j 之间的关系：

特点：

#define MAXV 100
#define INF 0x3f3f3f3f         // 用一个大数表示"无穷大/不可达"
typedef struct {
    int vexnum, edgenum;       // 顶点数、边数
    int edge[MAXV][MAXV];      // 邻接矩阵
    // (可再加一个数组存每个顶点的信息,如名字)
} MGraph;

适用：稠密图（边多，矩阵不浪费）；需要频繁判断两点是否相连。

4.3.2 邻接表（适合稀疏图）

为每个顶点建一个单链表，把「从该顶点出发能直接到达的所有邻居」串在这个链表上。n 个顶点就有 n 个链表（用一个数组管理这些链表的头）。

特点：

typedef struct ArcNode {       // 边节点(链表里的一个邻居)
    int             adjvex;    // 该边指向的顶点编号
    int             weight;    // 边的权值(带权图用)
    struct ArcNode *next;      // 指向下一条边
} ArcNode;

typedef struct {               // 顶点节点(数组里的一项)
    int      data;             // 顶点信息
    ArcNode *first;            // 指向该顶点的第一条边
} VNode;

typedef struct {
    VNode vertices[MAXV];      // 顶点数组,每个挂一条边链表
    int   vexnum, edgenum;
} ALGraph;

适用：稀疏图（省空间）；需要频繁遍历某顶点的邻居（如 DFS/BFS、最短路）。

4.3.3 对比总结（必考，做成表）

对比维度 邻接矩阵 邻接表
空间 O(n²)，与边数无关 O(n+e)，与边数相关
适合 稠密图 稀疏图
判断 i、j 是否相连 O(1) O(该顶点的度)
找一个顶点所有邻居 O(n) 扫一行 O(度)，更快
求度 数一行/列 出度易、入度难（有向）
是否对称 无向图对称 —

⚠️ 邻接矩阵易错点（判断题）： ①「邻接矩阵对称 ⟹ 一定是无向图」是错的——有向图若每条弧都恰好成对出现（<i,j> 和 <j,i> 都有），矩阵也对称。② 无向图邻接矩阵中，第 i 行（或第 i 列）非零元个数 = 顶点 i 的度；有向图中，第 i 行非零元个数 = 出度，第 i 列非零元个数 = 入度。③ 无向图邻接矩阵存储空间可只存下三角（对称），但一般仍按 n² 算。

4.3.4 其它存储（了解）

了解名字和用途即可，重点掌握邻接矩阵和邻接表。

4.4 图的遍历（DFS 与 BFS，核心基础）

和树的遍历一样，图也要能「不重不漏地访问每个顶点」。但图比树麻烦：图可能有环，顺着边走可能转圈圈无限循环。所以图遍历必须额外用一个 visited[] 数组标记每个顶点是否已访问过，访问过的不再访问，避免死循环。这是图遍历和树遍历最大的区别，务必记住。

两种基本遍历：DFS（深度优先）和 BFS（广度优先），分别对应「一头扎到底」和「一圈圈扩散」。

思想：从某顶点出发，沿一条路一直往深走，走到不能再走（邻居都访问过了）就回退到上一个分叉点，换另一条没走过的路继续。像走迷宫时「一直往前走，撞墙了就退回上一个路口换方向」。

实现：天然用递归（递归本身就借助系统栈），也可用一个栈显式实现。

int visited[MAXV];             // 标记数组,初始全 0(未访问)

// 从顶点 v 出发深度优先遍历(邻接矩阵版)
void DFS(MGraph *G, int v) {
    visit(v);                  // 访问 v(比如打印)
    visited[v] = 1;            // 标记为已访问
    for (int w = 0; w < G->vexnum; w++) {        // 找 v 的所有邻居 w
        if (G->edge[v][w] != 0 && !visited[w]) { // 有边 且 w 还没访问过
            DFS(G, w);                            // 递归深入 w
        }
    }
}

// 主调:处理"图不连通"——可能一次 DFS 走不完所有点,要对每个未访问点都启动一次
void DFSTraverse(MGraph *G) {
    for (int i = 0; i < G->vexnum; i++) visited[i] = 0;
    for (int i = 0; i < G->vexnum; i++)
        if (!visited[i]) DFS(G, i);   // 每启动一次 DFS = 发现一个连通分量
}

复杂度：每个顶点访问一次、每条边检查一次。邻接表存储 O(n+e)；邻接矩阵存储 O(n²)（因为找邻居要扫一整行）。

一个重要副产品：在 DFSTraverse 里，外层循环每启动一次新的 DFS，就说明发现了一个新的连通分量。所以 DFS 能用来数连通分量个数 / 判断图是否连通。

思想：从某顶点出发，先访问它的所有直接邻居（第一圈），再访问邻居的邻居（第二圈）……像往水里扔石头，波纹一圈圈向外扩散。

实现：用队列（和树的层序遍历完全一样的机制！）。

void BFS(MGraph *G, int v) {
    Queue Q; InitQueue(&Q);
    visit(v); visited[v] = 1;          // 访问起点并标记
    EnQueue(&Q, v);                    // 起点入队
    while (!QueueEmpty(&Q)) {
        int u; DeQueue(&Q, &u);        // 取出一个顶点
        for (int w = 0; w < G->vexnum; w++) {        // 遍历它的所有邻居
            if (G->edge[u][w] != 0 && !visited[w]) { // 有边且没访问过
                visit(w); visited[w] = 1;            // 访问并标记
                EnQueue(&Q, w);                       // 邻居入队,等下一圈处理
            }
        }
    }
}

复杂度：同 DFS，邻接表 O(n+e)，邻接矩阵 O(n²)。

BFS 的杀手锏：在无权图里，BFS 从起点出发，第一次到达某个顶点时走过的边数，就是到它的最短路径（最少边数）。因为 BFS 是一圈圈扩散的，先到的一定是近的。所以无权图求最短路用 BFS。（带权图的最短路要用 Dijkstra，见 6.6）

4.4.3 DFS vs BFS 对比

DFS 深度优先 BFS 广度优先
策略 一条路走到黑，再回退 一圈圈向外扩散
借助结构 栈 / 递归 队列
类比 走迷宫钻到底 水波纹扩散
典型用途 连通性、找路径、拓扑、判环 无权图最短路、层次遍历
复杂度 邻接表 O(n+e)、矩阵 O(n²) 同左

记忆锚点：DFS 用栈/递归（深→栈），BFS 用队列（广→队列）。这和前面树的「层序遍历用队列」是同一回事。

4.4.4 DFS/BFS 遍历序列演示

例图（无向图，邻接关系，遍历时按顶点编号从小到大选下一个）：

V0 - V1, V2
V1 - V0, V3, V4
V2 - V0, V5, V6
V3 - V1
V4 - V1, V6
V5 - V2
V6 - V2, V4

DFS（从 V0 出发，一条路走到底再回退）：

BFS（从 V0 出发，一圈圈扩散，用队列）：

对比体会：DFS 像「钻到底」（V0→V1→V3 一头扎进去），BFS 像「按层摊开」（先把 V0 的所有邻居访问完再下一层）。遍历序列依赖于「邻居访问顺序」的约定（这里规定按编号从小到大），换了存储方式或约定，序列可能不同——考试题一般会说明约定。

4.5 最小生成树 MST（必考）

4.5.1 问题

给一个带权连通无向图（比如 n 个城市，边权是修路成本），要把所有城市连通，且总成本最小。答案就是这个图的最小生成树（Minimum Spanning Tree, MST）——用 n−1 条边连通所有 n 个顶点、且边权之和最小、无环。两个经典贪心算法：Prim 和 Kruskal。

4.5.2 Prim 算法（「加点」，适合稠密图）

思想：从任意一个顶点开始，把顶点分成「已在树里的」和「还没进树的」两拨。每一步，在所有「一端在树里、一端在树外」的边中，选权值最小的那条，把它和它连接的树外顶点拉进树。重复 n−1 次，所有顶点入树，MST 完成。

直觉：像滚雪球，从一个点开始，每次吸纳「离当前这棵树最近的」一个新顶点。

Prim 过程:
1. 任选一个起点放入树 T。
2. 重复 n-1 次:
   在连接 "T 内顶点" 和 "T 外顶点" 的所有边中,
   挑权值最小的边 (u, v)（u 在 T 内, v 在 T 外）,
   把 v 和这条边加入 T。
3. T 就是最小生成树。

复杂度：朴素实现 O(n²)（每次找最小边要扫顶点），和边数无关，所以适合稠密图（边多时不吃亏）。

4.5.3 Kruskal 算法（「加边」，适合稀疏图）

思想：完全从边的角度。把所有边按权值从小到大排序，然后从最小的边开始一条条考察：如果加入这条边不会形成环，就加入；会成环就跳过。直到选够 n−1 条边，MST 完成。

直觉：贪心地总挑当前最便宜的边，只要它能连接两个还没连通的部分（不成环）。

怎么判断「会不会成环」？ 用并查集（5.14 节）！一条边连接的两个顶点，如果它们已经在同一个集合（已连通），再加这条边就成环——跳过；否则加入并 Union 这两个集合。这正是并查集的经典应用。

Kruskal 过程:
1. 把所有边按权值升序排序。
2. 初始化并查集(每个顶点自成一组)。
3. 依次取最小的边 (u, v):
   若 Find(u) != Find(v)（不在同一组,加了不成环）:
       选这条边, Union(u, v)。
   否则跳过(会成环)。
4. 选够 n-1 条边即完成。

复杂度：主要花在排序，O(e log e)，和顶点数关系小，所以适合稀疏图（边少时排序快）。

4.5.4 完整演示：同一个图跑 Prim 和 Kruskal

例图（6 个顶点 A~F，边及权值如下）：

边:  A-B=6  A-C=1  A-D=5  B-C=5  C-D=5  B-E=3  C-E=6  C-F=4  D-F=2  E-F=6

Kruskal（加边，按权排序选）：先把所有边升序排：

A-C(1), D-F(2), B-E(3), C-F(4), A-D(5)/B-C(5)/C-D(5), A-B(6)/C-E(6)/E-F(6)

依次考察（用并查集判环）：

边 权 两端是否已连通 选/弃 当前已选边数
A-C 1 否 选 1
D-F 2 否 选 2
B-E 3 否 选 3
C-F 4 否（{A,C}与{D,F}合并） 选 4
A-D 5 是（A、D 已都在 {A,C,D,F}） 弃（成环） 4
B-C 5 否（把 {B,E} 接入） 选 5 ✓

选够 n−1=5 条边，停止。MST 的边：A-C(1), D-F(2), B-E(3), C-F(4), B-C(5)，总权 = 1+2+3+4+5 = 15。

Prim（加点，从 A 开始）：每轮选「一端在树内、一端在树外」的最小边。

轮次 树内顶点 候选最小边 加入的点和边
起 {A} — 起点 A
1 {A} A-C=1 最小 加 C，边 A-C(1)
2 {A,C} C-F=4 < C-D=5 < A-D=5 < B-C=5 加 F，边 C-F(4)
3 {A,C,F} F-D=2 最小 加 D，边 D-F(2)
4 {A,C,D,F} B-C=5（A-B=6,C-E=6 更大） 加 B，边 B-C(5)
5 {A,B,C,D,F} B-E=3 最小 加 E，边 B-E(3)

MST 的边：A-C(1), C-F(4), D-F(2), B-C(5), B-E(3)，总权 = 15。

注意两个算法选的边完全一样（本图 MST 唯一），总权都是 15。验证了「Prim 加点、Kruskal 加边，殊途同归」。若图里有等权边，两者选的边可能不同，但总权一定相等。

4.5.5 对比与记忆

Prim Kruskal
策略 加点（从一个点长出整棵树） 加边（按边权从小到大选）
关键工具 找最近的树外点 排序 + 并查集判环
复杂度 O(n²) O(e log e)
适合 稠密图（点少边多） 稀疏图（边少）

记忆口诀：Prim 加点（适合稠密）、Kruskal 加边（适合稀疏）。 注意 MST 可能不唯一（有等权边时），但最小总权值唯一。考试常考：给一个带权图，手动跑 Prim 或 Kruskal，画出 MST 并求总权值。

⚠️ MST 易错点（判断题）： ① MST「不是简单地挑 n−1 条最小的边」——必须保证连通且无环（挑边时会成环的要跳过，所以选的不一定是绝对最小的那 n−1 条）。② 当所有边权互不相同时，MST 唯一；有等权边时才可能不唯一。③ MST 恰好 n−1 条边、连通、无环（它本身是一棵生成树）。

4.6 最短路径（必考，Dijkstra 爱考填表）

4.6.1 问题

带权图里，求从一个顶点到另一个顶点（或所有顶点）的权值之和最小的路径。注意：这里是「权之和最小」，不是「边数最少」（边数最少是无权图的 BFS 解决的）。两个经典算法。

4.6.2 Dijkstra 算法（单源最短路，最爱考）

用途：求一个源点到其余所有顶点的最短路径。限制：不能有负权边（有负权要用别的算法）。

思想（贪心 + 逐步确定）：维护每个顶点「目前已知的从源点到它的最短距离」dist[]，初始只有源点是 0、其余是 ∞。每一步，从还没确定的顶点里挑出 dist 最小的那个，把它「确定」下来（它的最短距离从此不再变），然后用它去松弛（更新）它的邻居们的 dist——「从源点经过我，到你的邻居，会不会比你原来记录的更近？若更近就更新」。重复直到所有顶点确定。

「松弛」是关键操作：对刚确定的顶点 u 的每个邻居 v，若 dist[u] + 权(u,v) < dist[v]，就更新 dist[v] = dist[u] + 权(u,v)。

Dijkstra 过程(源点 s):
1. dist[s] = 0, 其余 dist[] = ∞; 所有顶点标记为"未确定"。
2. 重复 n 次:
   a. 在所有"未确定"的顶点里, 选 dist 最小的顶点 u, 标记 u 为"已确定"。
   b. 对 u 的每个未确定邻居 v 做松弛:
      若 dist[u] + 权(u,v) < dist[v], 则 dist[v] = dist[u] + 权(u,v)。
3. 最终 dist[] 就是源点到各顶点的最短距离。

为什么不能有负权边？ 因为 Dijkstra 一旦「确定」一个顶点就再不改它，这建立在「已确定的就是最优、后面不会更短」的假设上。若存在负权边，后面可能出现一条经过负权的更短路径，但那个顶点已经被错误地确定了，结果就错。所以负权用 Dijkstra 会出错，这是必考的坑。

复杂度：朴素 O(n²)，用堆优化可到 O(e log n)。

考点——手动填表：这是 Dijkstra 最经典的题型。给一个带权图和源点，画一张表，每一行是一轮：列出本轮确定了哪个顶点、以及更新后各顶点的 dist 值。一轮轮填下去。

完整填表演示

例图（有向带权图，源点 V0，5 个顶点 V0~V4）：

弧:  V0→V1=10   V0→V4=5
     V1→V2=1    V1→V4=2
     V2→V3=4
     V3→V0=7    V3→V2=6
     V4→V1=3    V4→V2=9   V4→V3=2

逐轮填表（∞ 表示暂不可达，加粗表示本轮被更新的值，✓ 表示本轮被「确定」的顶点）：

轮次 确定的点 V1 V2 V3 V4
初始 V0(=0) 10 ∞ ∞ 5
1 V4(=5，未定中最小) 8(经V4:5+3) 14(5+9) 7(5+2) ✓
2 V3(=7) 8 13(经V3:7+6,比14小) ✓ ✓
3 V1(=8) ✓ 9(经V1:8+1,比13小) ✓ ✓
4 V2(=9) ✓ ✓ ✓ ✓

每轮做了什么，逐行解释：

最终最短距离：V0→V1=8，V0→V2=9，V0→V3=7，V0→V4=5。

填表口诀：每轮先在「未确定」列里挑 dist 最小的确定它（打✓），再拿它去松弛还没确定的邻居（能更短就改小）。务必自己按这张图独立填一遍对答案——这是机械送分大题，唯一会丢分的就是粗心。

4.6.3 Floyd 算法（所有点对最短路）

用途：一次求出任意两个顶点之间的最短路径（不是单源，是「全源」）。可以处理负权边（但不能有负权环）。

思想（动态规划，极简洁）：用邻接矩阵 A[i][j] 存当前 i 到 j 的最短距离。然后枚举每一个顶点 k 作为「中转站」，看「i 经过 k 到 j」是不是比「i 直接到 j」更短，更短就更新。三重循环，外层是中转点 k，内层是所有点对 (i, j)：

// Floyd 算法核心:A 初始为邻接矩阵(无边为 ∞,对角为 0)
for (int k = 0; k < n; k++)             // k:枚举中转点(必须在最外层!)
    for (int i = 0; i < n; i++)         // i:起点
        for (int j = 0; j < n; j++)     // j:终点
            if (A[i][k] + A[k][j] < A[i][j])    // 经过 k 更短?
                A[i][j] = A[i][k] + A[k][j];    // 更新
// 结束后 A[i][j] 就是 i 到 j 的最短距离

注意 k 必须在最外层循环——这是 Floyd 正确性的关键（含义是「允许用前 k 个顶点做中转」逐步放开），写错层次结果就错，是常考陷阱。

复杂度：三重循环 O(n³)。代码极短但是立方级，适合顶点数不大、要求所有点对距离的场景。

4.6.4 对比

Dijkstra Floyd
求什么 单源（一个点到其余所有） 全源（所有点对之间）
能否负权 不能有负权边 可以（不能有负权环）
思想 贪心 动态规划
复杂度 O(n²) O(n³)
代码 较长，要选最小+松弛 极短，三重循环

4.7 拓扑排序与关键路径（有向无环图的应用）

4.7.1 拓扑排序（AOV 网，必考）

背景（AOV 网）：很多任务之间有先后依赖关系——比如选课，「数据结构」必须先修「C 语言」。把活动作为顶点、依赖作为有向边的图叫 AOV 网（Activity On Vertex，顶点表示活动）。

拓扑排序：给这些有依赖关系的活动排出一个合法的线性顺序，使得每个活动都排在它所有「前置依赖」的后面。比如给一堆课程的先修关系，排出一个能依次修完的选课顺序。

算法（基于入度）：

拓扑排序过程:
1. 求每个顶点的入度。
2. 把所有入度为 0 的顶点(没有前置依赖的)入队/入栈。
3. 重复:
   a. 取出一个入度为 0 的顶点 v, 输出它。
   b. 删除 v 及其所有出边——即把 v 指向的每个邻居的入度减 1。
   c. 若某邻居入度减到 0, 也加入队列。
4. 直到所有顶点都输出。

两个关键考点：

完整演示

例图（有向图，箭头表示「先→后」依赖）：

弧:  V0→V1   V0→V2   V0→V3
     V1→V4
     V2→V4   V2→V5
     V3→V5
     V4→V5

先算各顶点初始入度：

顶点 V0 V1 V2 V3 V4 V5
入度 0 1 1 1 2 3

逐步执行（每次输出一个入度为 0 的点，删它的出边、相应邻居入度减 1）：

步 输出 删除后入度变化 当前入度为0的点
1 V0 V1→0, V2→0, V3→0 V1,V2,V3
2 V1 V4→1 V2,V3
3 V2 V4→0, V5→2 V3,V4
4 V3 V5→1 V4
5 V4 V5→0 V5
6 V5 — —

一个合法拓扑序列：V0 V1 V2 V3 V4 V5。

注意「不唯一」：第 2 步时 V1、V2、V3 都入度为 0，先输出谁都行。若先输出 V2，序列就变成 V0 V2 ...。所以本图还有 V0 V2 V1 V3 V4 V5、V0 V3 V1 V2 V4 V5 等多个合法解。考试若问「下列哪个是合法拓扑序列」，逐个验证「每个点都在它的所有前驱之后」即可。

另一种做法：DFS 拓扑排序（了解）。 对图做 DFS，在每个顶点递归返回（退出）时把它压入一个栈；全部 DFS 完后，把栈里的顶点依次弹出，得到的就是一个拓扑序列（即「DFS 逆后序」）。直觉：一个顶点只有等它指向的所有后继都处理完才退出，所以它在栈里更靠上、更先被弹出、排在前面。这个方法只适用于无环图（DFS 中若遇到指向「正在递归栈中」的顶点说明有环）。

4.7.2 关键路径（AOE 网，必考会算）

背景（AOE 网）：用边表示活动、边权表示活动持续时间、顶点表示事件（状态）的有向无环带权图，叫 AOE 网（Activity On Edge）。常用于工程进度管理：每条边是一道工序，权是工期。

关键路径：从开始顶点到结束顶点的最长的那条路径（路径长度=边权之和）。为什么是「最长」？因为工程要全部工序完成才算完工，而最长的那条路决定了整个工程最少需要多久——再快也快不过这条最长链。所以关键路径 = 工程的最短完成时间。

关键活动：位于关键路径上的活动。它们没有任何「机动时间」，一旦拖延，整个工程就跟着延期。所以工程管理要死盯关键活动。

四个量的定义（务必记牢，符号别混）：

对每个事件（顶点）v 算两个时间：

对每个活动（边）a = <u→w> 算两个时间：

⭐ 完整手算演示（必背套路）

例 AOE 网（源点 V1、汇点 V6，边上是活动耗时）：

弧(活动,耗时):
  V1→V2 = 3    V1→V3 = 2
  V2→V4 = 2    V3→V4 = 4
  V3→V5 = 3    V4→V6 = 2
  V5→V6 = 1

第一步：正向求 ve（拓扑序从源点推，取最大）

事件 V1 V2 V3 V4 V5 V6
ve 0 3 2 max(3+2, 2+4)=6 2+3=5 max(6+2, 5+1)=8

总工期 = ve(V6) = 8。

第二步：逆向求 vl（从汇点倒推，取最小）。先令 vl(V6)=ve(V6)=8。

事件 V6 V5 V4 V3 V2 V1
vl 8 8−1=7 8−2=6 min(6−4, 7−3)=2 6−2=4 min(4−3,2−2)=0

第三步：对每条边（活动）算 e、l、d=l−e

活动 边 e=ve(起点) l=vl(终点)−耗时 d=l−e 关键?
a1 V1→V2(3) 0 4−3=1 1
a2 V1→V3(2) 0 2−2=0 0 ★
a3 V2→V4(2) 3 6−2=4 1
a4 V3→V4(4) 2 6−4=2 0 ★
a5 V3→V5(3) 2 7−3=4 2
a6 V4→V6(2) 6 8−2=6 0 ★
a7 V5→V6(1) 5 8−1=7 2

关键活动：a2、a4、a6 → 关键路径 V1→V3→V4→V6，长度 2+4+2 = 8 = 总工期。✓

做题口诀：① ve 正着推取大（顶点按拓扑序）；② vl 倒着推取小（顶点逆拓扑序，汇点 vl=ve）；③ 边的 e=起点 ve、l=终点 vl 减耗时；④ e=l 的边就是关键活动。务必照这张图独立算一遍对答案。

⚠️ 易错点（判断题高频）：

4.8 图自测

  1. 有向图和无向图的边表示有什么不同？什么是入度、出度？
  2. n 个顶点的无向完全图、有向完全图各有多少边？
  3. 邻接矩阵和邻接表各适合稠密图还是稀疏图？空间复杂度分别多少？
  4. 判断两点是否相连，邻接矩阵和邻接表谁快？找一个点的所有邻居呢？
  5. 图遍历为什么必须有 visited 数组？（和树遍历的区别）
  6. DFS 用什么结构？BFS 用什么结构？BFS 在无权图里有什么特殊用途？
  7. Prim 和 Kruskal 各是「加点」还是「加边」？各适合什么图？Kruskal 怎么判环？
  8. Dijkstra 求什么？为什么不能有负权边？手动跑一个小图的 Dijkstra 填表。
  9. Floyd 求什么？复杂度多少？三重循环里 k 为什么必须在最外层？
  10. 拓扑排序的算法步骤？怎么用它判断有向图有没有环？结果唯一吗？
  11. 关键路径是最长路还是最短路？为什么它决定工程最短工期？什么是关键活动？

4.9 本段总自测清单

树的概念与性质

遍历

查找树

图

树与图两章到此结束。 这是全课最重的部分，硬骨头集中：遍历与还原、BST 删除、AVL 四种旋转、哈夫曼构造、Dijkstra 填表、Prim/Kruskal、拓扑排序。这些都是「会了就送分、不会就丢大块」的题，务必动手画图、手算到熟练，光读会有「看懂了一做就错」的错觉。

读完、自测过关后，下面进入第五、六章：查找表 + 排序 + 算法设计策略（收尾，含哈希、各排序算法对比与模拟、分治/贪心/DP/回溯）。读的过程中任何卡壳，随时回头复习。