#图

#考点定位

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

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

#零、图的基本概念与术语（严格定义）

• 图 $G = (V, E)$：顶点（数据元素）的非空有限集合 $V$ 与边（顶点间关系）的有限集合 $E$。与树（一对多、有层次）不同，图中任意两顶点都可能相关。
• 无向图 / 有向图：无方向的边记 $(u, v)$，$(u,v)$ 与 $(v,u)$ 是同一条边；有方向的边称弧，记 $\langle u, v \rangle$，$u$ 为弧尾、$v$ 为弧头。全部边为无向边的图称无向图，反之为有向图。
• 度：与顶点相关联的边数。有向图中分入度（以该顶点为弧头的弧数）与出度（以该顶点为弧尾的弧数），顶点的度 = 入度 + 出度。边与度的恒等式：无向图全部顶点度数之和 $= 2e$；有向图 $\sum\text{入度} = \sum\text{出度} = e$。
• 简单图：不存在自环（顶点到自身的边）、且任意两顶点间至多一条边的图（408 默认讨论简单图）；允许重边的称多重图。完全图：任意两顶点间都有边——无向完全图 $n$ 个顶点恰 $\frac{n(n-1)}{2}$ 条边，有向完全图恰 $n(n-1)$ 条弧。稠密图 / 稀疏图：边数接近完全图 / 远小于 $n^2$ 的图。
• 带权图（网）：每条边（弧）上附有一个数值（权）的图；下文最小生成树、最短路径讨论的都是网。
• 路径与回路：从顶点 $u$ 到 $v$ 的路径是一个顶点序列，路径上的边数称路径长度；顶点不重复的路径称简单路径；首尾顶点相同的路径称回路（环）。
• 连通与连通分量（无向图）：两顶点间存在路径则称连通；任意两顶点都连通的无向图称连通图；无向图的极大连通子图称连通分量（"极大"指再加入任何顶点或边都不再连通）。
• 强连通（有向图）：两顶点相互可达（存在双向路径）称强连通；任意两顶点都强连通的有向图称强连通图；有向图的极大强连通子图称强连通分量。含 $n$ 个顶点的强连通有向图最少 $n$ 条弧（构成一个大环）。
• 子图、生成子图与生成树：满足 $V' \subseteq V$、$E' \subseteq E$（且边所依附顶点均在 $V'$ 内）的 $G'=(V',E')$ 称子图；$V' = V$ 的子图称生成子图；连通图的包含全部 $n$ 个顶点的极小连通子图（$n-1$ 条边、无环）称生成树，非连通图各连通分量的生成树构成生成森林。最小生成树即权值和最小的生成树。
• 拓扑序列：将有向图的所有顶点排成一个线性序列，使图中任意弧 $\langle u, v\rangle$ 都满足 $u$ 排在 $v$ 之前（求法见下文拓扑排序）。

#一、图的存储结构

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

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

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

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

#二、图的遍历

#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 递归栈深 $O(n)$（最坏链形图），BFS 队列 $O(n)$。

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

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

#三、最小生成树（MST）

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

对比结论：Prim $O(n^2)$ 适合稠密图（复杂度只与点数相关）；Kruskal $O(e \log e)$ 适合稀疏图（排序主导，边少时快；配合并查集判环，并查集的定义与操作见 05-树与二叉树）。

共用例题（模拟题）：无向带权连通图，顶点 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 与外部的最小边"。

总权值 $= 1 + 4 + 2 + 5 + 3 = 15$。

Kruskal（分步表）：边按权升序逐一尝试，不成环则入选（用并查集判；并查集的单步演示与路径压缩对照见交互演示）。

总权值 $= 1 + 2 + 3 + 4 + 5 = 15$，与 Prim 一致（MST 总权唯一，边集可能不同）。

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

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

#四、最短路径

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

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

例（模拟题，有向网，源点 $v_0$）：弧：$v_0{\to}v_1$=10，$v_0{\to}v_3$=5，$v_1{\to}v_2$=1，$v_1{\to}v_3$=2，$v_2{\to}v_4$=4，$v_3{\to}v_1$=3，$v_3{\to}v_2$=9，$v_3{\to}v_4$=2，$v_4{\to}v_0$=7，$v_4{\to}v_2$=6。

最终：dist = $[0, 8, 9, 5, 7]$。注意轮 2 → 轮 3：$v_1$ 入 S 后用弧 $v_1{\to}v_2$=1 把 $v_2$ 从 13 松弛到 9——已确定的点（$v_4$=7）永不回改。

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

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

#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 循环的含义：$A^{(k)}[i][j]$ = 只允许经过编号 $\le k$ 的顶点作中转时 $i \to j$ 的最短路径长。k 必须在最外层——中间层的 k 不是"允许 1..k 中转"，这是代码填空/改错题的经典坑。
• 复杂度 $O(n^3)$、空间 $O(n^2)$（滚动使用同一矩阵）。
• 能处理负权边，但不能存在负权回路（有负环则最短路无定义，算法给出错误结果而不报错）。
• 小例验证（模拟题）：三点 1、2、3，$1{\to}2$=2，$2{\to}3$=3，$1{\to}3$=10。$k=2$ 时 $A[1][3] = \min(10, 2+3) = 5$——三重循环跑完就是传递闭包式的逐步改进。

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

#六、关键路径（AOE 网）

#术语与记号

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

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

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

AOE 网：事件 1..6；活动 $a_1$:1→2 权 4，$a_2$:1→3 权 3，$a_3$:2→4 权 6，$a_4$:2→5 权 5，$a_5$:3→4 权 5，$a_6$:3→6 权 7，$a_7$:4→6 权 4，$a_8$:5→6 权 3。

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

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

第 3 步，逐活动算 $e$、$l$、$d$：

第 4 步，串关键活动：$1 \to 2 \to 4 \to 6$，工期 $= 4 + 6 + 4 = 14$（与 $ve6 = 14$ 互检 ✓）。

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

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

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

#七、图算法设计题精练

#题 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);
}

复杂度：邻接表下 $O(n + e)$。变式：求连通分量个数——外层循环对所有未访问顶点调用 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 回溯入栈，再弹栈打印
}

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

#常见坑

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

#自测

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

答案与简析

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

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