#图

#考点定位

• 所属大纲章节：图的基本概念；图的存储（邻接矩阵、邻接表、十字链表、邻接多重表）；图的遍历；最小生成树；最短路径；拓扑排序；关键路径
• 常见题型：选择题（存储结构辨析、遍历复杂度、MST 性质、Dijkstra/Floyd 特性、拓扑序列判定、关键路径计算与缩短工期）；算法设计题（连通性判断、无权最短路、DFS/BFS 框架变形）
• 考查频率：极高。图的算法是 408 选择题的"计算量大户"（分步演算年年出现），Dijkstra 演算表与关键路径计算几乎轮流转考

工程直觉迁移：Dijkstra 就是你天天调用的最短路（OSPF 路由协议同源），拓扑排序就是构建系统的依赖解析。考试特有内容是手工分步演算的表格规范与各种"为什么不能/不唯一"的性质辨析——选择题分全在这里。

#一、图的存储结构

#邻接矩阵 vs 邻接表（对比表，选择题高频）

工程直觉：邻接矩阵是二维 bool 数组，邻接表就是 bucket 链。408 常考"无向图邻接表边结点总数 = $$"、逆邻接表解决入度这两点。

#十字链表与邻接多重表（辨析）

一句话辨析（选择题秒杀）：十字链表配有向图（弧），邻接多重表配无向图（边）；两者共同的动机都是"一条边/弧只存一次，兼顾两个端点的链"。

#二、图的遍历

#DFS 与 BFS（框架）

bool visited[MAXV];
void DFS(Graph G, int v) {              // 递归版；邻接矩阵与邻接表只换"找邻接点"方式
    visited[v] = true;  visit(v);
    for (v 的每个邻接点 w)
        if (!visited[w]) DFS(G, w);
}
void BFS(Graph G, int v) {
    visited[v] = true;  EnQueue(Q, v);
    while (!IsEmpty(Q)) {
        DeQueue(Q, w);  visit(w);
        for (w 的每个邻接点 u)
            if (!visited[u]) { visited[u] = true; EnQueue(Q, u); }
    }
}

#复杂度结论（必背）

空间：DFS 递归栈深 $$（最坏链形图），BFS 队列 $$。

#遍历的非唯一性与连通性应用

1. 遍历序列不唯一：同一图、同一存储，序列取决于对邻接点的枚举次序；邻接表本身表示不唯一。选择题问"DFS 序列唯一吗"，默认不唯一（除非图有特殊结构）。
2. 非连通图：一次 DFS/BFS 只能遍历一个连通分量；对所有顶点循环调用，调用次数 = 无向图连通分量数。有向图同理（弱/强连通要看具体条件）。
3. 生成树/生成森林：遍历经过的边集构成生成树（连通图）或生成森林（非连通图）；DFS 生成树高、BFS 生成树矮（广）。
4. BFS 的隐藏技能：无权图（各边权相等）中 BFS 首次到达某顶点所走路径即单源最短路径（按层数递增扩散）——选择题与算法题都用得上。

#三、最小生成树（MST）

#Prim（加点法）与 Kruskal（加边法）

对比结论：Prim $$ 适合稠密图（复杂度只与点数相关）；Kruskal $$ 适合稀疏图（排序主导，边少时快；配合并查集判环）。

共用例题（模拟题）：无向带权连通图，顶点 1..6，边及权：1-2:6，1-3:1，1-4:5，2-3:5，2-5:3，3-4:5，3-5:6，3-6:4，4-6:2，5-6:6。

Prim 从顶点 1 出发（分步表）：维护"已入选点集 U"与"跨越 U 与外部的最小边"。

总权值 $$。

Kruskal（分步表）：边按权升序逐一尝试，不成环则入选（用并查集判）。

总权值 $$，与 Prim 一致（MST 总权唯一，边集可能不同）。

#"T 性质"类选择题（MST 性质）

• 切割性质（横切边性质）：把点集切成两半，跨越切口的边中权最小者必属于某个最小生成树。
• 推论 1：若某条边是唯一最小横切边，则它属于每一个 MST（必选边）。
• 推论 2：图中权值最小的边（若唯一）必在每个 MST 中；权值最大的边不必然出局（但若它是唯一横切口最大边且删除后图仍连通，则必不在 MST 中）。
• MST 唯一性：所有边权互不相同时 MST 唯一；有相同权边时 MST 可能不唯一，但总权值恒唯一。
• 反例意识：权值最小的边若有并列多条，未必每条都在 MST 中（成环时只能取部分）。

#四、最短路径

#Dijkstra：单源，非负权（分步演算表）

流程：集合 S 存"已确定最短路"的点；每轮从 S 外选 dist 最小者入 S，并用它松弛其出边。

例（模拟题，有向网，源点 $$）：弧：$$=10，$$=5，$$=1，$$=2，$$=4，$$=3，$$=9，$$=2，$$=7，$$=6。

最终：dist = $$。注意轮 2 → 轮 3：$$ 入 S 后用弧 $$=1 把 $$ 从 13 松弛到 9——已确定的点（$$=7）永不回改。

为何不能处理负权边：算法的核心不变式是"每轮入 S 的点其 dist 已达最终值"——因为所有边权非负，任何绕行路径 $$ 当前 dist。存在负权边时，后入 S 的点可能通过负边反过来缩短已出确定的点，贪心前提崩溃。选择题标准问法：Dijkstra 求出的"最短路"在有负权时不保证正确。

复杂度：邻接矩阵 $$；邻接表 + 优先队列 $$（408 记结论 $$ 即可）。另一性质：按路径长度递增次序逐个产生最短路径。

#Floyd：每对顶点，三重循环

for (k = 1; k <= n; k++)          // 中转点：逐步允许 1..k 作为中转
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (A[i][k] + A[k][j] < A[i][j])
                A[i][j] = A[i][k] + A[k][j];   // 可同步维护 path[i][j] = k

• k 循环的含义：$$ = 只允许经过编号 $$ 的顶点作中转时 $$ 的最短路径长。k 必须在最外层——中间层的 k 不是"允许 1..k 中转"，这是代码填空/改错题的经典坑。
• 复杂度 $$、空间 $$（滚动使用同一矩阵）。
• 能处理负权边，但不能存在负权回路（有负环则最短路无定义，算法给出错误结果而不报错）。
• 小例验证（模拟题）：三点 1、2、3，$$=2，$$=3，$$=10。$$ 时 $$——三重循环跑完就是传递闭包式的逐步改进。

#Dijkstra vs Floyd（速查）

#五、拓扑排序

#方法一：入度法（ Kahn ）

反复输出入度为 0 的顶点并删除其所有出边（后继入度减 1）。实现：栈/队列存当前入度 0 的点。若输出顶点数 < n，说明存在回路（环上点入度永不为 0）。

例（模拟题）：弧 a→b，a→c，b→d，c→d，d→e。入度：a:0，b:1，c:1，d:2，e:1。过程：出 a → b、c 同时入度 0 →（栈内可任取）出 b → d 入度 1 → 出 c → d 入度 0 → 出 d → 出 e。可得 a b c d e 或 a c b d e——拓扑序列不唯一；但任何合法序列中 a 必首、e 必尾。选择题验证法：拿选项逐条检查"每条弧的起点是否排在终点之前"。

#方法二：DFS 出栈序的逆序

对有向无环图做 DFS，每个顶点完成时刻（所有后继递归返回、顶点出活动栈）的逆序是一个拓扑序。原理：完成某点时其全部后继必已完成，故它排在所有后继之后。判环：DFS 中遇到"正在访问中（在递归栈上）"的后向边则有环。

细节坑：是逆序不是出栈序；每轮从不同未访问点出发时，各轮结果按"轮次逆序拼接"理解（教材上一律加虚源点）。

#性质速查

1. 拓扑序列存在 $$ 有向图无环（DAG）。
2. 拓扑序列不唯一是常态；唯一当且仅当每一步恰有一个入度 0 的候选（图近于链）。
3. AOV 网（顶点表活动、边表约束）用拓扑排序；AOE 网（边表活动）求关键路径。

#六、关键路径（AOE 网）

#术语与记号

AOE 网：边（弧）表示活动、顶点表示事件，边权为活动持续时间。源点（入度 0，唯一）、汇点（出度 0，唯一）。

关键活动：$$（$$）的活动；关键路径：源点到汇点全部由关键活动组成的路径 = 最长路径；工期 = 关键路径长度。

#完整流程（例题，模拟题）

AOE 网：事件 1..6；活动 $$:1→2 权 4，$$:1→3 权 3，$$:2→4 权 6，$$:2→5 权 5，$$:3→4 权 5，$$:3→6 权 7，$$:4→6 权 4，$$:5→6 权 3。

第 1 步，按拓扑序求 $$（顺推取 max）：

第 2 步，按逆拓扑序求 $$（逆推取 min，汇点 $$）：

第 3 步，逐活动算 $$、$$、$$：

第 4 步，串关键活动：$$，工期 $$（与 $$ 互检 ✓）。

自查三件套：$$ 表逐格再算一遍；关键活动 $$ 且其 $$（首尾事件也是关键的）；工期 = $$(汇点) = 关键路径边权之和。

#缩短工期类选择题（陷阱重灾区）

1. 缩短任一关键活动的时长，整个工期不一定缩短——关键路径可能不止一条，缩的是"某一条"上的活动，另一条没变，工期不变。
2. 只有缩短所有关键路径共同经过的关键活动，才一定缩短总工期。
3. 关键活动缩短到一定程度后会失去关键地位（$$ 变为 0 再变正），继续缩无效——"缩短量超过该活动可压缩上限后工期不再减少"。
4. 缩短非关键活动（$$）对工期毫无贡献（在余量内）。
5. 关键活动一定处于关键路径上、其首尾事件的 $$；"关键路径是源到汇最长路径"与"最短路径无任何关系"（方向相反的考点拼接是常见干扰项）。

#七、图算法设计题精练

#题 1：判断无向图是否连通

题面：无向图 G 用邻接表存储，设计算法判断其是否连通。

思路：从任一顶点做一次 DFS/BFS，统计访问到的顶点数，等于 n 即连通。非连通时一次遍历只能覆盖一个连通分量。

伪代码：

bool Connected(ALGraph G) {
    for (i = 0; i < G.vexnum; i++) visited[i] = false;
    int count = 0;
    DFS_Count(G, 0, &count);          // 从 0 号顶点遍历并计数
    return count == G.vexnum;
}
void DFS_Count(ALGraph G, int v, int *count) {
    visited[v] = true;  (*count)++;
    for (ArcNode *p = G.vertices[v].first; p; p = p->nextarc)
        if (!visited[p->adjvex]) DFS_Count(G, p->adjvex, count);
}

复杂度：邻接表下 $$。变式：求连通分量个数——外层循环对所有未访问顶点调用 DFS，统计调用次数。

#题 2：无权图单源最短路径（BFS）及路径还原

题面：无权（各边权相等）有向图用邻接表存储，求源点 u 到其余各点的最短路径并输出 u 到 v 的一条最短路径。

思路：BFS 按层扩散，首次到达即最短。增设 dist[]（初始化 ∞，源点 0）与 path[]（记录前驱顶点），出队时对未访问邻接点登记 dist 与 path 再入队。输出路径从 v 沿 path[] 回溯到 u 后逆序打印。

伪代码：

void BFS_ShortestPath(ALGraph G, int u, int v) {
    for (i = 0; i < G.vexnum; i++) { dist[i] = INF; path[i] = -1; }
    dist[u] = 0;  visited[u] = true;  EnQueue(Q, u);
    while (!IsEmpty(Q)) {
        DeQueue(Q, w);
        for (ArcNode *p = G.vertices[w].first; p; p = p->nextarc) {
            int x = p->adjvex;
            if (!visited[x]) {
                visited[x] = true;
                dist[x] = dist[w] + 1;     // 首达即最短
                path[x] = w;               // 前驱，回溯用
                EnQueue(Q, x);
            }
        }
    }
    // 输出 u 到 v：沿 path 从 v 回溯入栈，再弹栈打印
}

复杂度：$$。评分要点：入队前标记 visited（防重复入队）；dist 更新只在首次访问时（BFS 层序保证首达最短，之后不再更新——与 Dijkstra 的多轮松弛对照记忆）。

#常见坑

1. 无向图邻接表边结点 $$ 个；有向图（出边表）$$ 个。邻接矩阵判断"顶点 i 的度"无向看行和，有向图行和是出度。
2. 十字链表 = 有向图、邻接多重表 = 无向图，配对反了是送分陷阱。
3. DFS/BFS 在邻接矩阵下都是 $$，别把"邻接表 $$"无脑套到矩阵上。
4. Dijkstra 负权失效；Floyd 负边可用、负环不可用；两者可解问题范围（单源 vs 每对）不同。
5. Floyd 的 k 必须在最外层；若写在内层，得到的不是"逐步放开中转点"的 DP，结果可能错（代码题与判断题双料考点）。
6. 拓扑排序选的是入度 0（不是出度 0）；DFS 法取完成序的逆；输出数 < n ⇔ 有环。
7. AOE 网里：$$ 顺推取 max、$$ 逆推取 min——考场上把 max/min 用反是关键路径题第一大失分点。活动余量 $$，关键活动 $$。
8. MST 总权唯一但树形可能不唯一（等权边）；Prim/Kruskal 各自适合的图密度相反（稠密 Prim、稀疏 Kruskal）。
9. 关键路径是最长路径；"缩短关键活动必缩短工期"是 408 最爱设的错误选项，用"多条关键路径"反驳。

#自测

1. 有 $$ 个顶点、$$ 条弧的有向图采用邻接表（出边表）存储，求每个顶点的入度的时间复杂度是多少？
2. 含 $$ 个顶点的强连通有向图最少几条边？无向连通图（含 $$ 顶点）最少几条边？
3. 某 AOE 网关键路径唯一且长度为 20，把该路径上某关键活动缩短 3 天后（该活动仍为正时长），工期一定变为 17 吗？
4. Kruskal 构造 MST 过程中判断"加入边 (u,v) 是否成环"用什么数据结构最合适？
5. 对 5 个顶点的图，Floyd 算法三重循环共执行多少次松弛判断？空间（距离矩阵）多大？

答案与简析

1. 需遍历全部 $$ 个边结点为各弧头计数，加上初始化 $$，共 $$。若同时建了逆邻接表则可 $$ 内直接读——但"遍历全表计数"是标准答案口径。
2. 强连通有向图最少 $$ 条边（一个大环，每点出度入度各 1）；无向连通图最少 $$ 条（树）。
3. 不一定。若缩短后该活动仍有余量结构变化（或另有等长关键路径），则只有当该路径仍为唯一关键路径时工期才降为 17；若图中还有另一条长 20 的关键路径则工期不变；若原路径领先幅度小于 3，新工期由次长路径决定。结论：不保证 17。
4. 并查集：查 u、v 根是否相同（相同则成环弃边，不同则合并）。这也是 Kruskal $$ 中判环开销近线性的原因。
5. 三重循环 $$ 次判断；距离矩阵 $$ 个单元（滚动使用，无需按轮存副本）。

下一步：图一章计算量大，务必限时完成 测验/02-树与图-章节测 中第 14-25 题，Dijkstra 与关键路径的分步演算各重做一遍（不看讲解）。