第7章图论算法及综合应用

🎯 本章学习目标

通过本章的学习，你将能够：

掌握最小生成树：理解MST概念，掌握Kruskal和Prim算法
掌握Kruskal算法：能手写Kruskal（边排序+并查集），知道时间复杂度
掌握Prim算法：理解Prim的贪心加点思想，知道稠密图更优
掌握Dijkstra算法：能手写Dijkstra单源最短路，知道不能处理负权边
掌握Floyd算法：能写Floyd全源最短路，知道k在最外层
理解并查集：掌握路径压缩和按秩合并，用于Kruskal判环
对比各算法：清楚各算法的适用场景和复杂度
图论建模：能把实际问题转化为图论问题（顶点/边/边权）
处理细节问题：知道重边、自环、不可达、long long等细节
应对真题题型：能解决选择、判断、编程等各类图论题目

🗺️ 本章知识图谱

图论算法及综合应用
├── 最小生成树（MST）
│   ├── 定义：连通、n-1条边、总权值最小
│   ├── 性质：边权互异则MST唯一
│   ├── Kruskal算法
│   │   ├── 核心：边排序 + 并查集，贪心加边
│   │   ├── 步骤：边按权排序→依次加（不环则加）
│   │   ├── 时间：O(m log m)
│   │   └── 适合：稀疏图
│   └── Prim算法
│       ├── 核心：从顶点出发，贪心加点
│       ├── 步骤：选最近点→更新距离
│       ├── 时间：O(n²) / 堆优化O(m log n)
│       └── 适合：稠密图
├── 最短路径
│   ├── Dijkstra（单源）
│   │   ├── 核心：贪心，每次选最近点松弛
│   │   ├── 不能处理负权边
│   │   ├── 时间：O(n²) / 堆优化O(m log n)
│   │   └── 适合：非负权图
│   ├── Floyd（全源）
│   │   ├── 核心：DP，枚举中转点k
│   │   ├── k必须在最外层
│   │   ├── 时间：O(n³)
│   │   ├── 可以处理负权边
│   │   └── 适合：n小（如≤200）
│   └── BFS（无权图单源）
│       ├── 时间：O(n+m)
│       └── 只适用于无权图
├── 并查集（DSU）
│   ├── 操作：find（找根）、unite（合并）
│   ├── 路径压缩
│   ├── 按秩合并
│   ├── 应用：Kruskal判环
│   └── 近似O(1)
├── 算法选型
│   ├── 全部连通总费用最小 → MST
│   ├── 起点到终点最快 → 最短路
│   ├── 稀疏图MST → Kruskal
│   ├── 稠密图MST → Prim
│   ├── 单源非负权 → Dijkstra
│   └── 全源/n小 → Floyd
├── 常见细节
│   ├── 无向图加边两次
│   ├── 重边取最小值
│   ├── 不可达输出-1
│   ├── 用long long防溢出
│   └── 初始化INF要足够大
└── 综合应用
    ├── 修路/通信（MST）
    ├── 导航/最短时间（最短路）
    ├── 图论建模三问：点？边？边权？
    └── 最短路计数

一、📖 为什么图论是八级的"重头戏"？

打开八级考卷你会发现：选择题、判断题里有图论概念辨析，编程大题里更常见"修路""导航""网络时延"这类图论应用题。原因很简单——图论算法同时考到了：

贪心思想（Kruskal 选边、Dijkstra 选点）
动态规划思想（Floyd 的三重循环）
高级数据结构（并查集、优先队列/堆）
建模能力（把文字题抽象成顶点和边）

🔥 高频考点：四大算法的复杂度排序、适用前提（尤其是 Dijkstra 的"非负权"、Floyd 的"无负环"）、算法过程模拟（手动跑 Kruskal/Prim/Dijkstra），几乎每场必考。

七级的知识储备（邻接表、DFS/BFS）本章默认已掌握，我们先花一小节把两种存储结构和并查集写成可直接套用的模板。

本章学习路线建议：第二节的两个模板是"地基"，务必先敲进电脑跑通；第三、四节按"思想→步骤→手算→代码→复杂度→易错点"的固定节奏推进，每个算法学完立刻用纸笔脱离代码手推一遍小图；第五节把前四节的工具"反向"用于建模；第六节六道例题按难度递进，前两道是选择判断热身，后三道（修路、网络时延、路径计数）覆盖编程大题的主流考法。

二、🧰 前置工具：图的存储 + 并查集

2.1 邻接矩阵 vs 邻接表

存储方式	空间	查一条边	遍历邻接点	适合
邻接矩阵	O(V²)	O(1)	O(V)	稠密图、V 小（≤1000）、Floyd
邻接表	O(V+E)	O(度)	O(度)	稀疏图、Kruskal/Prim/Dijkstra

C++11：

cpp

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

// —— 邻接矩阵（带权图，无边存 INF）——
// int g[1005][1005];
// memset(g, 0x3f, sizeof(g));
// for (int i = 1; i <= n; i++) g[i][i] = 0;
// g[u][v] = min(g[u][v], w);   // 有向图
// g[v][u] = g[u][v];           // 无向图补上这一句

// —— 邻接表 ——
int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);  // adj[u] = { {v, w}, ... }
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});              // 无向图：反向再加一条
    }
    for (auto &p : adj[1]) cout << p.first << "," << p.second << "\n";
    return 0;
}

2.2 并查集（Disjoint Set Union）

并查集是 Kruskal 的"判环神器"，支持两种操作：

find(x)：查 x 所在集合的"代表元素"（根），带路径压缩
unite(a,b)：合并两个集合，用按秩合并保证树不退化；若两点本就同集合，说明"加这条边会成环"

C++11：

cpp

struct DSU {
    vector<int> fa, rnk;
    DSU(int n) : fa(n + 1), rnk(n + 1, 0) {
        for (int i = 0; i <= n; i++) fa[i] = i;
    }
    int find(int x) {                          // 路径压缩
        return fa[x] == x ? x : fa[x] = find(fa[x]);
    }
    bool unite(int a, int b) {                 // 返回 true 表示成功合并
        a = find(a); b = find(b);
        if (a == b) return false;              // 已在同一集合 → 会成环
        if (rnk[a] < rnk[b]) swap(a, b);       // 按秩合并：小根挂大根
        fa[b] = a;
        if (rnk[a] == rnk[b]) rnk[a]++;
        return true;
    }
};

⚠️ 易错点：判环一定要用 find(u) == find(v)（比较根），而不是比较 fa[u] == fa[v]——父节点相同不代表同属一个集合！

三、🌳 最小生成树（MST）

3.1 概念

生成树：连通无向图中，选取全部 n 个顶点和恰好 n−1 条边，构成的连通且无环的子图（它本身是一棵树）。

最小生成树（Minimum Spanning Tree, MST）：在所有生成树中，边权总和最小的那一棵。

生活场景：n 个村庄修公路、n 栋楼铺光纤，要求"村村通"且总造价最低——就是 MST。

🔥 高频考点（性质速记）：
MST 含 n−1 条边、连接全部 n 个顶点、无环、连通；
边权互不相同时，MST 唯一；存在等权边时 MST 可能不唯一，但最小权值和一定唯一；
非连通图没有生成树，只有"最小生成森林"。

为什么生成树恰好 n−1 条边？ 树的等价定义之一是"n 个点、n−1 条边、连通且无环"。向树中加任意一条边必形成环（多余的边就是"浪费"），少一条边就不连通。所以 MST 就是在连通与无环的约束下，挑最便宜的 n−1 条边。

支撑两个算法的是 MST 的两条经典性质（理解即可，判断题常考）：

切分定理：把顶点任意分成两个集合 A、B，跨越两集合的边称为"横切边"，其中权值最小的横切边一定属于某棵 MST。Kruskal 每次连接两个连通分量时，选的就是当前这道"切分"的最小横切边；
环性质：图中任意一个环上，权值最大的边一定不在 MST 中（删掉它环就断开，树依然连通，且总权值更小）。Kruskal 跳过"会成环"的边，Prim 松弛时不选重边，本质都是这条性质。

3.2 Kruskal 算法（边贪心 + 并查集）

思想：把所有边按权值从小到大排序，依次尝试加入；若该边两端点已连通（加入会成环）就跳过，否则选中。直到选中 n−1 条边。

步骤：

所有边按 w 升序排序；
初始化并查集，每个点自成一个集合；
依次扫描边 (u,v,w)：unite(u,v) 成功则选中，累加 w；
选中 n−1 条边即结束；扫完仍不足 n−1 条，说明图不连通。

手动模拟（4 个顶点的无向带权图）：

边	(1,2,2)	(2,3,3)	(3,4,4)	(2,4,5)	(1,3,6)
排序后顺序	1	2	3	4	5

选 (1,2,2)：{1,2} 连通，累计 2
选 (2,3,3)：{1,2,3} 连通，累计 5
选 (3,4,4)：4 加入，全部连通，累计 9 ✅ 已选 3 = n−1 条，结束
(2,4,5)、(1,3,6) 两端早已同集合，会成环，跳过

MST 总权值 = 9，选中边：1-2、2-3、3-4。

C++11：

cpp

struct Edge { int u, v, w; };

int kruskal(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(),
         [](const Edge& a, const Edge& b) { return a.w < b.w; });
    DSU dsu(n);
    int sum = 0, cnt = 0;
    for (const Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {       // 不成环才选
            sum += e.w;
            if (++cnt == n - 1) break;   // 已构成生成树
        }
    }
    return cnt == n - 1 ? sum : -1;      // -1：图不连通
}

复杂度：排序 O(E log E)，并查集操作近似 O(E·α(V)) ≈ O(E)，总复杂度 O(E log E)，空间 O(V+E)。

⚠️ Kruskal 易错点： ① 边必须升序排序，写反成降序就变成"最大生成树"； ② 无向图每条边只存一次即可（有向图谈不上去做 MST）； ③ 循环里忘记"选中 n−1 条提前结束"不影响答案，但浪费时间； ④ 返回前要判断 cnt == n-1，否则非连通图会返回一个错误的小数。

3.3 Prim 算法（点贪心，类似 Dijkstra）

思想：从一个起点开始维护一个"已连通集合 S"。数组 dist[v] 表示顶点 v 到集合 S 的最短距离（即 v 连向 S 中任意点的最小边权）。每次把 dist 最小的点加入 S，并用它的边更新其余点的 dist。

步骤：

dist[起点]=0，其余为 INF；vis 全 false；
重复 n 次：选未访问中 dist 最小的 u，标记 vis，累加 dist[u]；
对 u 的每条边 (u,v,w)：若 v 未访问且 w < dist[v]，则 dist[v] = w；
若选出的 u 的 dist 为 INF，说明图不连通。

手动模拟（同一图，起点为 1）：

步骤	选中点	dist[2]	dist[3]	dist[4]	累计
初始	1	2（边1-2）	6（边1-3）	∞	0
1	2（dist=2）	✅	min(6, 3)=3（边2-3）	5（边2-4）	2
2	3（dist=3）	✅	✅	min(5, 4)=4（边3-4）	5
3	4（dist=4）	✅	✅	✅	9

C++11（朴素版 O(V²)）：

cpp

int prim(int n, const vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    dist[1] = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++)                    // 选 dist 最小的未访问点
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) return -1;       // 不连通
        vis[u] = true;
        sum += dist[u];
        for (const auto& p : adj[u]) {                  // 注意：松弛用边权 w
            int v = p.first, w = p.second;
            if (!vis[v] && w < dist[v]) dist[v] = w;
        }
    }
    return sum;
}

堆优化版思路：把"选最小 dist 的点"交给最小堆，每次弹出 (d, u)，用边更新后入堆——与下文 Dijkstra 堆优化几乎同构，复杂度降至 O(E log V)，适合稀疏图。对照代码如下（注意松弛仍是 w 而非 d + w）：

C++11（堆优化版）：

cpp

int primHeap(int n, const vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>>,
                   greater<pair<int,int>>> pq;
    dist[1] = 0;
    pq.push({0, 1});
    int sum = 0, cnt = 0;
    while (!pq.empty()) {
        pair<int,int> cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (vis[u]) continue;
        vis[u] = true;
        sum += d;                        // d 即 u 到集合的最小边权
        if (++cnt == n) break;
        for (const auto& p : adj[u]) {
            int v = p.first, w = p.second;
            if (!vis[v] && w < dist[v]) {
                dist[v] = w;             // 松弛用边权 w！
                pq.push({w, v});
            }
        }
    }
    return cnt == n ? sum : -1;
}

复杂度：朴素 O(V²)（稠密图反而更快）；堆优化 O(E log V)。

⚠️ Prim 易错点： ① Prim 松弛时写的是 dist[v] = w（v 到集合的直接边权），不是 dist[u] + w——写成后者就变成 Dijkstra 了，这是选择题/代码题经典陷阱； ② 起点 dist 初始化为 0，累加时第一条边贡献为 0，别多算； ③ 不连通判断不能少。

3.4 Kruskal vs Prim 对比（🔥 必考表）

对比维度	Kruskal	Prim
贪心对象	边：每次取最小且不成环的边	点：每次取离集合最近的点
核心工具	边集数组 + 并查集	dist 数组 + vis / 最小堆
时间复杂度	O(E log E)	朴素 O(V²)；堆优化 O(E log V)
最适合	稀疏图（E 小）	朴素版适合稠密图；堆版通吃
是否需要起点	不需要	需要指定起点
图不连通时	自然得到最小生成森林	需额外判断
记忆口诀	"排序、判环、选边"	"加点、更新、最近"

💡 数量级判断示例：n=1000 时，稠密图 E≈50 万，Kruskal 排序约 50万×log(50万) ≈ 950 万次比较，而朴素 Prim 仅 n²=100 万次扫描——稠密图选 Prim 朴素版；n=10⁵ 的稀疏图（E≈2×10⁵）则必须用 Kruskal 或堆优化 Prim，邻接矩阵连内存都放不下（n² = 10¹⁰）。这张"疏密选型"表第8期分析复杂度时还会用到。

四、🛣️ 最短路径

4.1 概念

单源最短路径：给定起点 s，求 s 到其余所有点的最短距离 → Dijkstra
全源（多源）最短路径：任意两点 i→j 的最短距离 → Floyd
无权图（或所有边权相等）的最短路，七级的 BFS 即可解决。

4.2 Dijkstra 算法（单源、非负权）

思想：贪心 + 松弛（relax）。维护 dist[]，每次从未确定最短路的点中选出 dist 最小的 u"定型"，再用 u 的每条边尝试松弛：

$dist[v] = \min(dist[v],\ dist[u] + w(u,v))$

为什么贪心正确？边权非负时，dist 最小的未定型点 u，不可能再通过其他未定型点绕路变得更短（绕路只会加上非负权值）。

步骤：

dist[s]=0，其余 INF；
重复：选未定型中 dist 最小的 u，标记定型；
用 u 的每条边松弛邻接点；
全部点定型（或堆空）结束。

手动模拟（无向带权图，起点 1；边：1-2:4，1-3:2，2-3:1，2-4:5，3-4:8，3-5:10，4-5:2）：

步骤	定型点	dist[2]	dist[3]	dist[4]	dist[5]
初始	1	4	2	∞	∞
1	3（d=2）	min(4,2+1)=3	✅	2+8=10	2+10=12
2	2（d=3）	✅	✅	min(10,3+5)=8	12
3	4（d=8）	✅	✅	✅	min(12,8+2)=10
4	5（d=10）	✅	✅	✅	✅

最短距离：1→5 = 10，路径 1→3→2→4→5（2+1+5+2）。

C++11（堆优化版 O(E log V)）：

cpp

vector<int> dijkstra(int s, int n, const vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n + 1, INF);
    priority_queue<pair<int,int>, vector<pair<int,int>>>,
                   greater<pair<int,int>>> pq;      // 最小堆：(距离, 点)
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        pair<int,int> cur = pq.top(); pq.pop();
        int d = cur.first, u = cur.second;
        if (d != dist[u]) continue;                // 过期条目，跳过
        for (const auto& p : adj[u]) {
            int v = p.first, w = p.second;
            if (dist[v] > d + w) {                 // 松弛
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

复杂度：朴素 O(V²)；堆优化 O(E log V)；空间 O(V+E)。朴素版完整代码见下文。

⚠️ Dijkstra 易错点（🔥 最高频）： ① 不能处理负权边！ 反例：s→a 权 5、s→b 权 6、b→a 权 −3。Dijkstra 先把 a 以 5 定型，但真实最短路 s→b→a = 3。贪心定型的前提就是权值非负； ② 堆优化版必须判断 d != dist[u] 跳过过期条目（一个点可能被多次入堆）； ③ 松弛式是 dist[u] + w，别和 Prim 的 w 混淆； ④ dist 数组要用足够大的 INF（C++ 常用 0x3f3f3f3f，且注意 INF+w 溢出问题）。

负权反例的完整推演（务必在草稿纸上跑一遍，胜过死记结论）：

步骤	堆顶	动作	dist[b]	dist[a]
初始	(0,s)	松弛：b←6，a←5	6	5
1	(5,a)	a 被错误定型为 5；a 无出边	6	5
2	(6,b)	b 松弛 a：6+(−3)=3 < 5，但 a 已定型，更新被忽略	6	5 ❌

正确答案 dist[a]=3，Dijkstra 却输出 5——错误根源正是"定型太早"。

📌 考纲边界说明：八级只要求掌握 Dijkstra（非负权）与 Floyd（可负权、无负环）。含负权边的单源问题属于 Bellman-Ford/SPFA 的范畴，不在八级要求内，但选择题常借负权边考查 Dijkstra 的适用前提，能举出上面这个反例即可。

C++11 朴素版 O(V²)（稠密图用，与 Prim 朴素版结构同构，注意松弛式差异）：

cpp

vector<int> dijkstraNaive(int s, int n, const vector<vector<pair<int,int>>>& adj) {
    vector<int> dist(n + 1, INF);
    vector<bool> vis(n + 1, false);
    dist[s] = 0;
    for (int i = 1; i <= n; i++) {
        int u = -1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) u = j;
        if (u == -1 || dist[u] == INF) break;
        vis[u] = true;
        for (const auto& p : adj[u]) {
            int v = p.first, w = p.second;
            if (dist[v] > dist[u] + w) dist[v] = dist[u] + w;  // 松弛：dist[u]+w
        }
    }
    return dist;
}

4.3 Floyd 算法（全源、动态规划）

思想：动态规划。定义 d[k][i][j] 表示从 i 到 j、中途只允许经过编号 ≤ k 的顶点时的最短距离。转移：

$d[k][i][j] = \min(d[k-1][i][j],\ \ d[k-1][i][k] + d[k-1][k][j])$

即"要么不经过 k，要么借道 k"。空间上可直接在同一个二维数组上滚动更新，得到经典三重循环。

步骤：

初始化：d[i][i]=0；有边存边权；无边存 INF；
k（中转点）在最外层，i、j 在内层；
转移 d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

手动模拟（有向图：1→2:3，1→3:8，2→3:2，3→4:1，2→4:9）：

k=2 时：d[1][3] = min(8, d[1][2]+d[2][3] = 3+2) = 5
k=3 时：d[1][4] = min(∞, d[1][3](已更新为5)+d[3][4] = 5+1) = 6；d[2][4] = min(9, 2+1) = 3

注意 d[1][3] 在 k=2 阶段被更新，k=3 阶段立刻被 d[1][4] 使用——这正是 k 必须在最外层的原因：中转点是 DP 的"阶段"。

C++11：

cpp

void floyd(int n, vector<vector<int>>& d) {   // d 初始化为邻接矩阵（含 INF）
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++) {
            if (d[i][k] == INF) continue;     // 防止 INF + w 溢出/误判
            for (int j = 1; j <= n; j++)
                if (d[k][j] < INF && d[i][k] + d[k][j] < d[i][j])
                    d[i][j] = d[i][k] + d[k][j];
        }
}

复杂度：时间 O(V³)，空间 O(V²)。V ≤ 400 左右可放心使用。

⚠️ Floyd 易错点： ① k 循环必须在最外层！写成 i-j-k 顺序结果全错（判断题常设此陷阱）； ② 初始化 d[i][i]=0，别留成 INF；无向图矩阵对称； ③ 可处理负权边，但不能有负环（负环存在时最短路无意义，跑完若 d[i][i] < 0 即存在负环）； ④ 加法前判断 INF，避免 INF+w 溢出后比真实距离还小。

Floyd 的两个实用小技巧：

负环检测：算法跑完后检查对角线，若存在 d[i][i] < 0，说明从 i 出发绕一圈回到 i 的总权值为负，图中存在负环，此时"最短路径"没有定义（可以无限绕环变小）。八级题目一般保证无负环，但这个判据要知道；
记录路径（前驱矩阵）：仅算距离有时不够，题目还要求输出方案。可维护 path[i][j]，初始无边时为 −1、有边时记为 i；当 d[i][j] 经 k 被更新时，同步 path[i][j] = path[k][j]。最后从 j 沿前驱回退即可还原整条路径。

💡 为什么 Floyd 能处理负权、Dijkstra 却不能？ Floyd 是动态规划：它枚举所有中转点、允许同一答案被反复松弛更新，不存在"定型后不许改"；Dijkstra 是贪心：点一旦弹出堆就被永久定型，负权边可能让"定型"后的距离再次变小，正确性无法保证。一句话——DP 允许反悔，贪心不允许。

4.4 BFS vs Dijkstra vs Floyd 对比（🔥 必考表）

对比维度	BFS	Dijkstra	Floyd
解决问题	单源最短路	单源最短路	全源最短路
权值要求	无权（或边权全相等）	非负权	可负权，不可有负环
核心思想	层序遍历	贪心 + 松弛	动态规划
核心结构	队列	dist 数组 + 最小堆	二维矩阵 + 三重循环
时间复杂度	O(V+E)	O(V²) / O(E log V)	O(V³)
空间复杂度	O(V+E)	O(V+E)	O(V²)
典型场景	迷宫步数、层级关系	导航、网络时延（大图）	V 很小、要全源、含负权

💡 一句话选型：无权用 BFS；单源非负用 Dijkstra；点很少（几百）要全源或有负权边用 Floyd。

两个进阶小技巧（小题也可能出现）：

多源最短路用"超级源点"：题目要求"离任意一个超市最近的距离"这类多源问题，不必跑多次 Dijkstra——建立一个虚拟起点 S，向所有源点连权 0 的边，从 S 跑一次 Dijkstra 即可；
Floyd 初始化代码模板：

cpp

// C++11
vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));
for (int i = 1; i <= n; i++) d[i][i] = 0;
for (每条边 u->v 权 w) d[u][v] = min(d[u][v], w);   // 无向图再加 d[v][u] = d[u][v]
floyd(n, d);

另外注意概念辨析：Dijkstra 定型过程中选出的边构成一棵以 s 为根的最短路径树，树上根到每个点的路径就是最短路径——它和 MST 是两棵不同的树，考题偶尔会把两者混在一起设问。

五、🧩 综合应用与建模技巧

5.1 建模三问

拿到一道应用题，先回答三个问题：

顶点是什么？（村庄、城市、主机、路口……）
边是什么？（公路、链路、航线……有向还是无向？）
边权是什么含义？（造价→MST 问题；距离/时延/费用→最短路问题）

题目特征	图模型	算法
"把所有点连起来，总造价最小"	无向带权图，选 n−1 条边	MST（Kruskal/Prim）
"从 A 到 B 最快/最短/最省"	带权图求两点距离	Dijkstra（非负）/ Floyd
"任意两点间的最短距离"	全源	Floyd
"最少经过几步/几个中转"	无权图	BFS
"能否连通 / 分成几个集合"	无向图连通性	并查集 / DFS

5.2 与前期知识块的综合

+ 计数原理（第2期）：最短路不只问"多短"，还问"最短路径有几条"。松弛时维护计数数组：dist[v] 被更新则 cnt[v]=cnt[u]；距离相等则 cnt[v]+=cnt[u]（本质是加法原理）。
+ 倍增思想（第5期）的影子：邻接矩阵 A 中 A[i][j] 表示 i→j 的边数；矩阵乘法改为"乘加"后，Aᵏ[i][j] 恰好等于从 i 到 j 经过 k 条边的路径（walk）条数——用矩阵快速幂（倍增）可在 O(V³ log k) 内求出，是"计数 + 倍增 + 图"三者交汇的经典拓展。
+ 贪心/DP：Kruskal、Dijkstra 是贪心；Floyd 是 DP；复习第8期复杂度分析时，本节四个复杂度 O(E log E)、O(V²)、O(E log V)、O(V³) 是最好的素材。

5.3 建模常见陷阱（编程大题的扣分重灾区）

陷阱	错误做法	正确做法
无向边只加一次	`adj[u].push(v)` 后忘记加反向边，图"半连通"	无向图加边两次；邻接矩阵 `g[u][v]=g[v][u]=w`
重边	直接覆盖，可能丢掉更优（更便宜）的边	MST 不影响（排序后自动选优）；邻接矩阵存 min；Floyd 初始化取 min
顶点编号	题目从 0 编号，数组按 1 起步读写	先看清编号范围，统一映射到 [1,n] 或 [0,n-1]
题意类型判断错	"村村通总造价"套 Dijkstra，"A 到 B 最快"套 MST	连所有点→MST；两点间最优路径→最短路
边权上界	int 累加 10⁵ 条 10⁴ 的边已到 10⁹，逼近 INT_MAX	边权/距离建议用 `long long` 更稳妥；INF 取 0x3f3f3f3f 仍小于 2³¹
不可达情况	直接输出 INF（0x3f3f3f3f 或 1061109567）	按题意转换输出 −1 / "impossible"

⚠️ 易错点：MST 题与最短路题的设问关键词务必圈出——"全部连通、总费用最小"是 MST；"从起点到终点、最快/最省"是最短路。两者边权含义相同、图也相同，但算法选错满盘皆输。

六、🏋️ 递进例题精解

例题1（选择题·MST 概念）

关于最小生成树，下列说法正确的是（　）
A. n 个顶点的最小生成树包含 n 条边 B. 任何无向图都存在最小生成树 C. 最小生成树可能不唯一，但其边权总和的最小值唯一 D. Kruskal 算法在任何图上都比 Prim 算法快

🔑 点击查看答案与解析

答案： C

A 错：生成树恰有 n−1 条边；
B 错：只有连通无向图才有生成树，非连通图只有最小生成森林；
C 对：存在等权边时 MST 可能有多棵，但最小权值和是确定值；边权互不相同则 MST 唯一；
D 错：稠密图上朴素 Prim（O(V²)）通常优于 Kruskal（O(E log E)）。

例题2（选择题·Kruskal 过程模拟）

无向带权图 4 个顶点，边为 (1,2,2)、(1,3,6)、(2,3,3)、(2,4,5)、(3,4,4)。Kruskal 算法按选中顺序选出的第三条边是（　）
A. (1,3,6)　　B. (2,4,5)　　C. (3,4,4)　　D. (2,3,3)

🔑 点击查看答案与解析

答案： C

边按权排序：2、3、4、5、6。依次判断：

(1,2,2)：1、2 不同集合 → 选中（第1条）；
(2,3,3)：3 不在 {1,2} → 选中（第2条）；
(3,4,4)：4 不在 {1,2,3} → 选中（第3条），已选 n−1=3 条，结束。

(2,4,5)、(1,3,6) 两端已同集合，成环跳过。MST 总权值 = 2+3+4 = 9。

例题3（判断题·算法前提与细节）

判断下列说法是否正确：
① 只要图中没有负权环，Dijkstra 就一定能正确求出单源最短路径。 ② Floyd 算法的三重循环中，i、j、k 的顺序可以任意交换。 ③ 若图中所有边权互不相同，则该图的最小生成树唯一。 ④ Kruskal 算法选中 n−1 条边后可以立即结束。

🔑 点击查看答案与解析

答案： ① ❌　② ❌　③ ✅　④ ✅

① 错。Dijkstra 的前提是所有边权非负。负权边即使不构成负环也会让"贪心定型"失效：反例 s→a=5、s→b=6、b→a=−3，算法把 a 以 5 定型，而真实最短路 s→b→a=3。无负环但含负权的场景应改用 Bellman-Ford/SPFA（超出八级要求，记住前提即可）；
② 错。k（中转点）是 DP 的阶段，必须在最外层；
③ 对。边权互异时，每一步贪心选择无歧义，MST 唯一；
④ 对。n−1 条边恰好连通 n 个点且无环，提前结束是标准优化。

例题4（综合应用·MST 修路问题）

题目：n 个村庄之间有 m 条候选公路，每条公路给出连接的两个村庄 u、v 和造价 w。求使所有村庄互相连通的最小总造价；若无论如何都无法全部连通，输出 −1。
样例输入：
4 5
1 2 2
1 3 6
2 3 3
2 4 5
3 4 4
样例输出：9

🔑 点击查看答案与解析

建模：村庄=顶点，公路=无向边，造价=边权。"全部连通且总造价最小"= 最小生成树，直接套 Kruskal。

解题要点：

边按造价升序排序；
并查集逐条尝试合并，合并成功则累加造价；
成功合并 n−1 次输出总造价；扫描结束仍不足 n−1 次，输出 −1（存在无法连通的村庄）。

C++11 核心代码（DSU 与 Edge 用 2.2/3.2 节模板）：

cpp

int main() {
    int n, m; cin >> n >> m;
    vector<Edge> edges(m);
    for (auto& e : edges) cin >> e.u >> e.v >> e.w;
    cout << kruskal(n, edges) << "\n";   // 内部已处理不连通返回 -1
    return 0;
}

样例中选中 1-2(2)、2-3(3)、3-4(4)，总造价 9。

🔥 变式提醒：若题目问"最多花多少钱"（最大生成树），把排序改成降序即可；若边有等级/必须选某些边，可先把必选边用并查集合并再跑 Kruskal。

例题5（综合应用·网络时延最短路）

题目：n 台主机由 m 条双向链路互联，每条链路有时延 t。求主机 1 到主机 n 的最小时延；不可达输出 −1。
样例输入：
5 7
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
3 5 10
4 5 2
样例输出：10

🔑 点击查看答案与解析

建模：主机=顶点，链路=无向边（双向记得加两次），时延=边权。时延非负 → Dijkstra 堆优化。

按 4.2 节手动模拟：dist[5] 最终为 10，路径 1→3→2→4→5（2+1+5+2）。

💡 建模确认：链路易双向通信，因此按无向边加两次。若题目改为"主机只能向编号更大的主机发包"这类带方向的描述，则为有向图，只加 u→v 一次——建模阶段务必逐字读题。

C++11 核心代码：

cpp

int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});      // 双向链路
    }
    vector<int> dist = dijkstra(1, n, adj);
    cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
    return 0;
}

---

例题6（综合提高·最短路径计数，融合第2期计数原理）

题目：在下图所示的无向带权图中（边：1-2:2，1-3:2，2-4:3，3-4:3，4-5:1），求顶点 1 到顶点 5 的最短距离，以及最短路径共有多少条（路径不同即边序列不同）。

🔑 点击查看答案与解析

答案： 最短距离 6，共 2 条最短路径（1→2→4→5 与 1→3→4→5，均为 2+3+1=6）。

方法：在 Dijkstra 松弛时同步维护计数数组 cnt（起点 cnt[s]=1）：

若 dist[v] > dist[u] + w：找到更短的路，dist[v] 更新，cnt[v] = cnt[u]（到 u 的最短路全部延伸过来）；
若 dist[v] == dist[u] + w：等长新路，cnt[v] += cnt[u]（加法原理，第2期知识）。

模拟：定型 2 时 d[4]=5、cnt[4]=1；定型 3 时 d[4] 仍为 5（2+3 相等）→ cnt[4]=2；定型 4 时 d[5]=6、cnt[5]=cnt[4]=2。

C++11 关键片段：

cpp

if (dist[v] > d + w) {
    dist[v] = d + w;
    cnt[v]  = cnt[u];          // 更短：覆盖计数
    pq.push({dist[v], v});
} else if (dist[v] == d + w) {
    cnt[v] += cnt[u];          // 等长：累加计数（数大时取模或用 long long）
}

⚠️ 计数可能很大，题目常要求对 1000000007 取模；且只有非负权图才能在 Dijkstra 中这样计数（定型后计数不再变）。

七、🎯 备考建议

模板必须会默写：并查集、Kruskal、Prim、Dijkstra（堆）、Floyd，五个模板各默写三遍；
手动模拟是选择题的生命线：考前用草稿纸把 Kruskal 选边、Dijkstra 定型各跑 2 个小图；
对比记忆：两张对比表（Kruskal vs Prim、BFS vs Dijkstra vs Floyd）建议抄在便利贴上；
易错点清单：Dijkstra 非负权、Floyd 的 k 在外层、Prim 松弛用 w 而 Dijkstra 用 dist[u]+w、并查集比根不比父——考前逐条自查。

八、✅ 考前自测清单

对照下表逐条打钩，全部"会"再上考场：

#	自测项	会了吗
1	说出 MST 的三个特征（n−1 边、连通、无环）及"边权互异则 MST 唯一"	⬜
2	并查集 find/unite 能默写，说出路径压缩与按秩合并的作用	⬜
3	给一张 4~5 点小图，能手跑 Kruskal 并写出选边顺序与总权值	⬜
4	能手跑 Prim，说清它的松弛用 `w`、Dijkstra 的松弛用 `dist[u]+w`	⬜
5	背出 Kruskal O(E log E)、Prim O(V²)/O(E log V) 及各自适用图的疏密	⬜
6	说明 Dijkstra 为什么不能处理负权边，并能画出 s→a=5、s→b=6、b→a=−3 反例	⬜
7	堆优化 Dijkstra 中 `d != dist[u]` 跳过过期条目的原因	⬜
8	Floyd 三重循环的正确顺序（k 在最外层）与动态规划含义	⬜
9	Floyd 能处理负权边、不能处理负环；负环检测看 `d[i][i] < 0`	⬜
10	BFS / Dijkstra / Floyd 的选型口诀与复杂度对比表能默写	⬜
11	读一道应用题能三问答建模：顶点是什么、边是什么、边权是什么含义	⬜
12	"全部连通总费用最小"→MST；"起点到终点最快"→最短路，关键词不混淆	⬜
13	最短路计数：更短则覆盖、等长则累加（加法原理），并记得取模	⬜
14	无向图加边两次、重边取 min、累加权值用 long long、不可达输出 −1	⬜

九、📝 实战练习

练习题 1（判断题）

题目： n 个顶点的最小生成树一定有 n-1 条边。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 最小生成树（MST）的三个基本性质：

包含所有 n 个顶点（连通）
恰好有 n-1 条边
没有环（树的定义）

总权值最小的生成树就是最小生成树。

💡 记忆：生成树 = 包含所有顶点的树（n个点，n-1条边，无环，连通）。

---

练习题 2（单选题）

题目： Kruskal 算法使用的数据结构和时间复杂度是？（）

A. 栈，O(n²)
B. 并查集，O(m log m)
C. 队列，O(n+m)
D. 堆，O(m log n)

🔑 点击查看答案与解析

答案： B

解析： Kruskal 算法：

把所有边按权值从小到大排序 → O(m log m)
依次尝试加入每条边
用并查集判断两个端点是否已经连通
不连通就合并（加入这条边）

主要时间花在排序上：O(m log m)

A 错误：不是栈
C 错误：BFS用队列
D 错误：Prim堆优化/Dijkstra堆优化用堆

选 B。

🍎 记忆口诀：Kruskal = 边排序 + 并查集（管边不管点）。

---

练习题 3（判断题）

题目： Dijkstra 算法可以处理带负权边的最短路径问题。（）

🔑 点击查看答案与解析

答案： 错误 ❌

解析： Dijkstra 算法不能处理负权边。

原因：Dijkstra 是贪心算法，每次选距离最小的顶点"确定"最短路。如果有负权边，后面可能出现更短的路径，但Dijkstra已经把那个顶点标记为"确定"了，不会再更新。

反例：s→a=5, s→b=6, b→a=-3

Dijkstra先选a（距离5），标记a确定
但实际上 s→b→a = 6 + (-3) = 3，更短
但a已经被标记为"确定"了，Dijkstra不会再更新

🔥 高频考点：Dijkstra不能处理负权边，是判断题和选择题的常客。有负权用Bellman-Ford/SPFA（八级不要求）。

---

练习题 4（单选题）

题目： Floyd 算法求全源最短路径的三重循环中，正确的顺序是？（）

A. i → j → k
B. k → i → j
C. i → k → j
D. 任意顺序都可以

🔑 点击查看答案与解析

答案： B

解析： Floyd 算法的正确写法：

cpp

for (k = 1; k <= n; k++)       // 中转点k在最外层
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            if (dist[i][k] + dist[k][j] < dist[i][j])
                dist[i][j] = dist[i][k] + dist[k][j];

为什么 k 必须在最外层？因为 Floyd 本质是 DP：

dp[k][i][j] = 允许经过前 k 个点中转时，i 到 j 的最短路
第 k 层依赖第 k-1 层的结果

k 在内层就会"用了还没算出来的结果"。

选 B。

🔥 必考考点：Floyd 的 k 在最外层！这句话一定要刻在脑子里。

---

练习题 5（单选题）

题目： "要在 n 个城市之间修建通信线路，使得所有城市连通且总费用最少"，这是什么问题？用什么算法？（）

A. 最短路问题，Dijkstra
B. 最小生成树问题，Kruskal
C. 拓扑排序问题
D. 二分图匹配问题

🔑 点击查看答案与解析

答案： B

解析： "所有城市连通" + "总费用最少" = **最小生成树（MST）**问题。

MST 算法：

Kruskal：边排序 + 并查集，适合稀疏图
Prim：贪心加点，适合稠密图

其他选项：

A 错误：最短路是"从一个点到另一个点"，不是"所有点连通"
C 错误：拓扑排序是DAG的问题
D 错误：二分图匹配是另一类问题

选 B。

💡 选型口诀："全部连通总费用最小" → MST；"起点到终点最快" → 最短路。

---

练习题 6（单选题）

题目： Prim 算法更适合什么类型的图？（）

A. 稀疏图
B. 稠密图
C. 有向图
D. 有环图

🔑 点击查看答案与解析

答案： B

解析：

Prim 算法：O(n²)（邻接矩阵实现），和边数无关，适合稠密图
Kruskal 算法：O(m log m)，和边数有关，适合稀疏图

为什么？

稠密图边多（m接近n²），Kruskal排序 O(n² log n) 比 Prim 的 O(n²) 慢
稀疏图边少，Kruskal更快

选 B。

💡 记忆：Prim管点（不管边）→ 点少边多（稠密）用Prim；Kruskal管边（不管点）→ 边少（稀疏）用Kruskal。

---

练习题 7（判断题）

题目： 并查集的路径压缩优化可以让 find 操作的时间复杂度接近 O(1)。（）

🔑 点击查看答案与解析

答案： 正确 ✅

解析： 并查集的两个优化：

路径压缩：find时把路径上的节点直接指向根，下次查找更快
按秩合并：把小树合并到大树下面，保持树平衡

两个优化都加上后，每次操作的时间复杂度接近 O(1)（准确说是反阿克曼函数，增长极慢，可以近似看作常数）。

💡 Kruskal算法高效的原因之一就是并查集几乎是O(1)的。

---

练习题 8（编程题）

题目： 给定 n 个顶点的有向图，求任意两点之间的最短路径长度。

输入：第一行 n, m（顶点数和边数），接下来 m 行每行 u, v, w（从u到v的边权为w）
输出：n 行，每行 n 个数，表示从 i 到 j 的最短路长度（不可达输出 -1）

样例输入：

样例输出：

0 5 7
-1 0 2
-1 -1 0

🔑 点击查看答案与解析

答案： 参考代码（Floyd 算法）：

cpp

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
int dist[105][105];

int main() {
    int n, m;
    cin >> n >> m;
    
    // 初始化
    memset(dist, 0x3f, sizeof(dist));
    for (int i = 1; i <= n; i++) {
        dist[i][i] = 0;
    }
    
    // 加边
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w < dist[u][v]) {  // 重边取最小
            dist[u][v] = w;
        }
    }
    
    // Floyd：k在最外层！
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 输出
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dist[i][j] >= INF / 2) cout << -1 << " ";
            else cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

解析： Floyd 算法步骤：

初始化距离矩阵（对角线为0，其余为INF）
读入边（注意重边取最小值）
三重循环：k → i → j（k在最外层）
松弛：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

🔥 必背：Floyd的k在最外层！三重循环共 O(n³)，n ≤ 200 时适用。

---

十、📊 考点总结表

考点	重要程度	出题形式	易错点
MST定义和性质	⭐⭐⭐⭐⭐	选择/判断	n个点n-1条边，无环，连通
Kruskal算法	⭐⭐⭐⭐⭐	编程题/选择	边排序+并查集，O(m log m)
Prim算法	⭐⭐⭐⭐	选择/判断	贪心加点，稠密图更优
Dijkstra算法	⭐⭐⭐⭐⭐	编程题/选择	不能处理负权边！
Floyd算法	⭐⭐⭐⭐⭐	编程题/选择/代码填空	k必须在最外层，O(n³)
并查集	⭐⭐⭐⭐⭐	代码填空/编程	路径压缩+按秩合并，近似O(1)
算法选型	⭐⭐⭐⭐⭐	选择/判断	MST vs 最短路，Kruskal vs Prim
负权边处理	⭐⭐⭐⭐	选择/判断	Dijkstra不能，Floyd可以（但不能有负环）
重边/自环	⭐⭐⭐⭐	编程细节	重边取最小值，自环不影响
INF初始化	⭐⭐⭐⭐	代码填空	0x3f3f3f3f约1e9，两个相加不溢出
不可达输出	⭐⭐⭐⭐	编程细节	输出-1，用INF/2判断（防止溢出）
图论建模	⭐⭐⭐⭐⭐	编程题	三问：顶点？边？边权？

⭐ 必背速记卡

┌─────────────────────────────────────────────┐
│       图论算法 · 必背速记卡                 │
├─────────────────────────────────────────────┤
│  1. MST：n个点，n-1条边，无环，总权最小     │
│  2. Kruskal：边排序+并查集，O(m log m)     │
│  3. Kruskal适合稀疏图                       │
│  4. Prim：贪心加点，O(n²)，适合稠密图       │
│  5. 全部连通总费用最小 → MST                │
│  6. 起点到终点最快 → 最短路                 │
│  7. Dijkstra：单源最短路，贪心选最近点       │
│  8. Dijkstra不能处理负权边！                 │
│  9. Floyd：全源最短路，O(n³)                │
│ 10. Floyd的k必须在最外层！                   │
│ 11. Floyd可以处理负权边，但不能有负环        │
│ 12. 并查集：find找根，unite合并             │
│ 13. 并查集路径压缩+按秩合并，近似O(1)        │
│ 14. 重边取最小值，无向图加两边               │
│ 15. INF用0x3f3f3f3f，不可达输出-1           │
└─────────────────────────────────────────────┘

第7章 图论算法及综合应用 ​

🎯 本章学习目标 ​

🗺️ 本章知识图谱 ​

一、📖 为什么图论是八级的"重头戏"？ ​

二、🧰 前置工具：图的存储 + 并查集 ​

2.1 邻接矩阵 vs 邻接表 ​

2.2 并查集（Disjoint Set Union） ​

三、🌳 最小生成树（MST） ​

3.1 概念 ​

3.2 Kruskal 算法（边贪心 + 并查集） ​

3.3 Prim 算法（点贪心，类似 Dijkstra） ​

3.4 Kruskal vs Prim 对比（🔥 必考表） ​

四、🛣️ 最短路径 ​

4.1 概念 ​

4.2 Dijkstra 算法（单源、非负权） ​

4.3 Floyd 算法（全源、动态规划） ​

4.4 BFS vs Dijkstra vs Floyd 对比（🔥 必考表） ​

五、🧩 综合应用与建模技巧 ​

5.1 建模三问 ​

5.2 与前期知识块的综合 ​

5.3 建模常见陷阱（编程大题的扣分重灾区） ​

六、🏋️ 递进例题精解 ​

例题1（选择题·MST 概念） ​

例题2（选择题·Kruskal 过程模拟） ​

例题3（判断题·算法前提与细节） ​

例题4（综合应用·MST 修路问题） ​

例题5（综合应用·网络时延最短路） ​

例题6（综合提高·最短路径计数，融合第2期计数原理） ​

七、🎯 备考建议 ​

八、✅ 考前自测清单 ​

九、📝 实战练习 ​

练习题 1（判断题） ​

练习题 2（单选题） ​

练习题 3（判断题） ​

练习题 4（单选题） ​

练习题 5（单选题） ​

练习题 6（单选题） ​

练习题 7（判断题） ​

练习题 8（编程题） ​

十、📊 考点总结表 ​

⭐ 必背速记卡 ​

第7章图论算法及综合应用

🎯 本章学习目标

🗺️ 本章知识图谱

一、📖 为什么图论是八级的"重头戏"？

二、🧰 前置工具：图的存储 + 并查集

2.1 邻接矩阵 vs 邻接表

2.2 并查集（Disjoint Set Union）

三、🌳 最小生成树（MST）

3.1 概念

3.2 Kruskal 算法（边贪心 + 并查集）

3.3 Prim 算法（点贪心，类似 Dijkstra）

3.4 Kruskal vs Prim 对比（🔥 必考表）

四、🛣️ 最短路径

4.1 概念

4.2 Dijkstra 算法（单源、非负权）

4.3 Floyd 算法（全源、动态规划）

4.4 BFS vs Dijkstra vs Floyd 对比（🔥 必考表）

五、🧩 综合应用与建模技巧

5.1 建模三问

5.2 与前期知识块的综合

5.3 建模常见陷阱（编程大题的扣分重灾区）

六、🏋️ 递进例题精解

例题1（选择题·MST 概念）

例题2（选择题·Kruskal 过程模拟）

例题3（判断题·算法前提与细节）

例题4（综合应用·MST 修路问题）

例题5（综合应用·网络时延最短路）

例题6（综合提高·最短路径计数，融合第2期计数原理）

七、🎯 备考建议

八、✅ 考前自测清单

九、📝 实战练习

练习题 1（判断题）

练习题 2（单选题）

练习题 3（判断题）

练习题 4（单选题）

练习题 5（单选题）

练习题 6（单选题）

练习题 7（判断题）

练习题 8（编程题）

十、📊 考点总结表

⭐ 必背速记卡