【数据结构】图论基础（BFS/DFS/prim/kruskal/dijkstra/BF/spfa/floyd)

目录

图的存储和遍历

最小生成树

Prim 算法

Kruskal 算法

拓扑排序

单源最短路

dijkstra 算法

Bellman-Ford 算法

spfa 算法

多源最短路 - floyd 算法

无向图的最小环问题

• 有向图和⽆向图：边有没有方向，可以将⽆向图中的边看成两条⽅向相反的有向边，从⽽将⽆向图转化为有向图
• 简单图与多重图：若图中没有重边和⾃环，为简单图。若图中存在重边或⾃环，为多重图。⾃环：⾃⼰指向⾃⼰的⼀条边。重边：图中存在两个或两个以上完全相同的边。题目没有明确说明没有重边或自环，默认有重边或自环。
• 稠密图和稀疏图：有很少条边的图称为稀疏图，反之称为稠密图。
• 顶点的度：顶点 v 的度是指与它相关联的边的条数，记作 deg(v)。由该顶点发出的边称为顶点的出度，到达该顶点的边称为顶点的⼊度。⽆向图中，顶点的度等于该顶点的⼊度和出度，有向图中，顶点的度等于该顶点的⼊度与出度之和
• 路径：在图 G = (V， E) 中，若从顶点 a 出发，沿⼀些边经过b，c顶点 ，到达 d 顶点 。则称顶点序列 ( a，b，c，d) 为从顶点 a 到顶点 d 的路径
• 简单路径与回路：若路径上各顶点 v1 , v2 , v3 , ..., vm 均不重复，则称这样的路径为简单路径。若路径上第⼀个顶点 v1 和最后⼀个顶点 vm 相同，则称这样的路径为回路或环。
• 路径⻓度和带权路径⻓度：某些图的边具有与它相关的数值，称其为该边的权值。这些权值可以表⽰两个顶点间的距离、花费的代价、所需的时间等。⼀般将该种带权图称为⽹络。对于不带权的图，⼀条路径的路径⻓度是指该路径上的边的条数。对于带权的图，⼀条路径的路径⻓度是指该路径上各个边权值的总和。
• 子图：就是在原来图的基础上，拿出来⼀些顶点和边，组成⼀个新的图。但是要注意，拿出来的点和边要能构成⼀个图才⾏。
• 生成子图：子图包含原图所有顶点
• 连通图与连通分量：在⽆向图中，若从顶点 a 到顶点 b 有路径，则称顶点 a 与顶点 b 是连通的。如果图 G 中任意⼀对顶点都是连通的，则图 G 称为连通图，否则称为⾮连通图。假设⼀个图有 n 个顶点，如果边数⼩于 n - 1，那么此图⼀定是⾮连通图。极⼤联通⼦图：在一个非连通图中，由于图不是全连通的，它必然由几个部分拼凑而成。每一个部分，如果满足以下两个条件，就称为极大连通子图：1、内部连通：这个子图本身是连通的（任意两个顶点之间存在路径）。2、外部极大：在原始图中，哪怕只往这个子图里多加入一个额外的顶点（以及与之相连的边），这个子图就会变得不连通。连通分量：⽆向图中的极⼤连通⼦图称为连通分量。
• ⽣成树：连通图的⽣成树是包含图中全部顶点的⼀个极⼩连通⼦图。若图中顶点数为 n，则它的⽣成树一定含有 n - 1 条边。对⽣成树⽽⾔，若砍去⼀条边，则会变成⾮连通图，若加上⼀条边则会形成⼀个回路。

图的存储和遍历

存储：三种：邻接矩阵和邻接表（孩子表示法、链式前向星）

邻接表孩子表示法：vector<pair<int,int>> edges[N]; edegs[u] = { v,w} 表示 u->v 权值 w,

遍历：bfs、dfs

bfs：

const int N = 100010; // 根据题目要求调整 vector<int> g[N]; // 邻接表存图 bool vis[N]; // 访问标记 int dist[N]; // 距离数组（可选） // 基础BFS模板 void bfs(int start) { queue<int> q; q.push(start); vis[start] = true; dist[start] = 0; while (!q.empty()) { int u = q.front(); q.pop(); // 处理当前节点u // cout << u << " "; for (int v : g[u]) { if (!vis[v]) { vis[v] = true; dist[v] = dist[u] + 1; q.push(v); } } } }

dfs：

// 基础DFS模板（递归） void dfs(int u) { vis[u] = true; // cout << u << " "; // 前序遍历 for (int v : g[u]) { if (!vis[v]) { dfs(v); } } // cout << u << " "; // 后序遍历 }

最小生成树

联通图的所有⽣成树中权值之和最⼩的树称为最⼩⽣成树，可能不唯一。求联通图的最小生成树可以使用 Prim 算法和 kruskal 算法

P3366 【模板】最小生成树 - 洛谷

Prim 算法

核⼼：不断加点。
Prim 算法构造最⼩⽣成树的基本思想：
1. 从任意⼀个点开始构造最⼩⽣成树；
2. 将距离该树权值最⼩且不在树中的顶点，加⼊到⽣成树中。然后更新与该点相连的点到⽣成树的最短距离；
3. 重复 2 操作 n 次，直到所有顶点都加⼊为⽌

题目：给出一个无向图，求出最小生成树。如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出orz

#include <iostream> #include <cstring> using namespace std; const int N = 5010, INF = 0x3f3f3f3f; int n, m; int edges[N][N]; // 邻接矩阵存储图 int dist[N]; // 某个点距离⽣成树的最短距离 bool st[N]; // 标记哪些点已经加⼊到⽣成树 int prim() { // 初始化 memset(dist, 0x3f, sizeof dist); dist[1] = 0; //将 1 号结点加入最小联通子图 int ret = 0; // 最终结果 for (int i = 1; i <= n; i++) // 循环加⼊ n 个点 { // 1. 找最近点 int t = 0; // 最近点的下标,一定从0开始！！！！！！！！！！！！ for (int j = 1; j <= n; j++) if (!st[j] && dist[j] < dist[t]) t = j; // 判断是否联通 if (dist[t] == INF) return INF; st[t] = true; ret += dist[t]; // 2. 更新距离 for (int j = 1; j <= n; j++) // 枚举 t 能⾛到哪 if(edges[t][j] != INF) dist[j] = min(dist[j], edges[t][j]); } return ret; } int main() { cin >> n >> m; // 这里初始化邻接矩阵的目的是不影响读入数据 memset(edges, 0x3f, sizeof edges); for (int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; // 注意有重边的情况，取边权最小的边 edges[x][y] = edges[y][x] = min(edges[x][y], z); } int ret = prim(); // prim 函数返回最小联通子图的权值之和 // 如果 ret 是 INF，说明原图是非联通图，不能构成最小联通子图 if (ret == INF) cout << "orz" << endl; else cout << ret << endl; return 0; }

Kruskal 算法

核⼼：不断加边。
Kruskal 算法构造最⼩⽣成树的基本思想：
1. 所有边按照权值排序；
2. 每次选出权值最⼩且两端顶点不连通的⼀条边，直到所有顶点都联通。

#include<iostream> #include<algorithm> #include<string.h> using namespace std; const int N = 5010; const int M = 1e6 + 10; #define INF 0x3f3f3f3f int n, m; struct edge { int x, y, z; }e[M]; int fa[N]; bool cmp(edge& e1, edge& e2) { return e1.z < e2.z; } int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); } int main() { cin >> n >> m; memset(e, 0x3f,sizeof(e)); for (int i = 1; i <= m; i++) { int x, y, z; cin >> x >> y >> z; e[i].x = x; e[i].y = y; if (z < e[i].z) e[i].z = z; } for (int i = 1; i <= n; i++) fa[i] = i; sort(e + 1, e + m + 1, cmp); int cnt = 0; int ret = 0; for (int i = 1; i <= m; i++) { int f1 = find(e[i].x); int f2 = find(e[i].y); if (f1 != f2) { cnt++; ret += e[i].z; fa[f1] = f2; } } if (cnt == n - 1) cout << ret; else cout << "orz"; return 0; }

拓扑排序

1. 什么是“有向无环图”（DAG）？

我们可以通过拆解这个术语来理解它：

• 图： 由顶点（或称为节点）和连接顶点的边组成的集合。

• 有向： 图中的边是有方向的。从顶点 A 到顶点 B 的边（A → B）与从 B 到 A 的边（B → A）是两条不同的边。这表示一种单向关系。

• 无环： 图中不存在任何循环。也就是说，你无法从任何一个顶点出发，沿着若干条有向边，最终又回到该顶点本身。

总结一下：
有向无环图就是一个带有方向边的图，并且你不可能从某个节点开始，沿着边的方向一直走，最终又回到起点。

2. 什么是AOV网？

AOV网是Activity On Vertex network的缩写，中文意思是“用顶点表示活动的网络”或“活动在顶点上的网络”。

它是一种特殊的有向图，用于描述一个项目中各个活动（任务）之间的优先约束关系。

• 顶点： 代表活动或任务。例如，一门课程、一个编译过程、一个生产步骤。

• 有向边： 代表活动之间的优先关系（即依赖关系）。如果存在一条从顶点 A 指向顶点 B 的有向边<A, B>，则表示活动 A 必须在活动 B 开始之前完成。A 称为 B 的直接前驱，B 称为 A 的直接后继。

核心特性：
由于AOV网描述的是“先后次序”，它绝对不能存在有向环。如果存在环，比如 A→B→C→A，就意味着 A 要在 B 之前完成，B 要在 C 之前完成，而 C 又要在 A 之前完成。这形成了一个逻辑悖论，项目将永远无法开始。因此，AOV网其实就是一个有向无环图。

拓扑排序

目标： 将 DAG 中的所有顶点排成一个线性序列，使得对图中任意一条有向边<u, v>，在序列中u都出现在v的前面。

通俗理解： 就像是为一系列有先后顺序的任务（比如上面的青椒炒肉工程图）安排一个线性可执行的清单。这个清单必须保证，所有前置任务都在后续任务之前完成。

重要性质：

• 存在性： 一个图能进行拓扑排序的充要条件是它是一个有向无环图。如果图中有环，拓扑排序就无法进行。

• 不唯一性： 一个 DAG 的拓扑排序序列可能有多个。

BFS 解决拓扑排序的算法实现

算法步骤：

1. 统计入度： 遍历图，计算每个顶点的入度（有多少条边指向它）。

2. 初始化队列： 将所有入度为 0的顶点加入一个队列（或栈、列表）。

3. 当队列不为空时循环处理：
   a. 从队列中取出一个顶点u，并将其输出（或存入结果列表）。
   b. 遍历u的所有邻接顶点v：

   • 将v的入度减 1（相当于从图中移除边<u, v>）。

   • 如果v的入度因此变为 0，则将v加入队列。

4. 当队列为空时检查结果：

   • 如果结果列表中的顶点数量等于图中的总顶点数，则排序成功，该列表即为拓扑排序之一。

   • 如果结果列表中的顶点数量小于总顶点数，说明图中存在环，无法进行拓扑排序。（拓扑排序的应用之一：判断有向图是否存在环）

拓扑排序不仅可以判断图是否存在环，还可以求环的大小，方法是进行一次拓扑排序把所有不在环的结点打上标记，然后用 bfs/dfs 遍历所有没有标记的结点。

B3644 【模板】拓扑排序 / 家谱树 - 洛谷

#include <iostream> #include <vector> #include <queue> using namespace std; const int N = 110; int n; vector<int> edges[N]; int in[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) { int j; while (cin >> j, j) { edges[i].push_back(j); in[j]++; } } queue<int> q; for(int i = 1; i <= n; i++) { if (in[i] == 0) q.push(i); } while (q.size()) { int cur = q.front(); q.pop(); cout << cur << ' '; for (auto m : edges[cur]) { in[m]--; if (in[m] == 0) q.push(m); } } return 0; }

单源最短路

在图中，假设 a 和 b 为图中的两个顶点，那么 a 到 b 路径上所经过边的权值之和就称为带权
路径⻓度。路径可能有多条，将带权路径⻓度最短的那条路径称为最短路径。求解单源最短路时，一定要注意题目的数据范围，如果边权非负，才可以使用dijkstra算法，如果出现负权边，就要使用 BF 算法和 spfa 算法

dijkstra 算法

Dijkstra (迪杰斯特拉)算法是基于贪⼼思想的单源最短路算法,求解的是⾮负权图上单源最短路径。

常规版 dijkstra 算法流程：（现假设求 1 到任意结点的最短路径）

• 准备⼯作：
◦ 创建⼀个⻓度为n的dist数组,全部初始化为无穷大,dist[i]表⽰起点到 i 结点的最短路；
◦ 创建⼀个⻓度为n的bool数组st,全部初始化为false,st[i]表⽰起点到 i 点是否确定了最短路。
• 初始化： dist[1] = 0 ，其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
• 重复n-1次：在所有没有确定最短路的点中，找出最短路⻓度最⼩的点 x 。打上确定最短路的标记，然后对 x 的出边进⾏松弛操作：

P3371 【模板】单源最短路径（弱化版） - 洛谷

不知道 2^31 - 1 等于多少怎么办？(int)pow(2,31) - 1;注意强转

#include <iostream> #include <vector> using namespace std; typedef pair<int, int> PII; const int N = 1e4 + 10, M = 5e5 + 10; const int INF = 2147483647; int n, m, s; vector<PII> edges[M]; int dist[N]; bool st[N]; void Dijkstra() { // 初始化 dist 数组 for (int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; // 循环 n - 1 次就行了 for (int i = 1; i <= n - 1; i++) { int a = 0;// 一定初始为 0 ！！！ // 找出 dist 最小的结点 for (int j = 1; j <= n; j++) { if (!st[j] && dist[j] < dist[a]) a = j; } st[a] = true; //确定最短路径 // 松弛操作 for (auto t : edges[a]) { int v = t.first, w = t.second; if (dist[a] + w < dist[v]) dist[v] = dist[a] + w; } } //打印结果 for (int i = 1; i <= n; i++) cout << dist[i] << ' '; } int main() { //输入数据 cin >> n >> m >> s; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({ v,w }); } Dijkstra(); //cout << (int)pow(2, 31) - 1 << endl; return 0; }

堆优化：

在上面的代码中，找出 dist 最小的结点采用暴力遍历的方式，其实可以把 pair<最短距离，结点> 放在优先级队列里面。

P4779 【模板】单源最短路径（标准版） - 洛谷

#include <iostream> #include <vector> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 1e5 + 10, M = 2e5 + 10; int n, m, s; vector<PII> edges[M]; int dist[N]; bool st[N]; priority_queue<PII,vector<PII>,greater<PII>> heap; // pair<最短距离，结点> void Dijkstra() { // 初始化 dist 数组 for (int i = 0; i <= n; i++) dist[i] = 0x3f3f3f3f; dist[s] = 0; heap.push({ 0,s }); while(heap.size()) { PII tmp = heap.top(); heap.pop(); int a = tmp.second; if (st[a]) continue; st[a] = true; //确定最短路径 // 松弛操作 for (auto& t : edges[a]) { int v = t.first, w = t.second; if (dist[a] + w < dist[v]) { dist[v] = dist[a] + w; heap.push({ dist[v] ,v }); } } } //打印结果 for (int i = 1; i <= n; i++) cout << dist[i] << ' '; } int main() { //输入数据 cin >> n >> m >> s; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({ v,w }); } Dijkstra(); return 0; }

Bellman-Ford 算法

Bellman‒Ford 算法(之后简称 BF 算法)是⼀种基于松弛操作的最短路算法，可以求出有负权的图的最短路，并可以对最短路不存在的情况进⾏判断。
算法核⼼思想：不断尝试对图上每⼀条边进⾏松弛，直到所有的点都⽆法松弛为⽌

最短路不存在的情况，即存在负环：负环：边权为负数的环路

从 1 到 4 不存在最短路，因为可以“最短路”可以环绕2、3、5结点所构成的环转无数圈从而达到负无穷

Bellman‒Ford 算法流程：（现假设求 1 到任意结点的最短路径）

• 准备⼯作：
◦ 创建⼀个⻓度为n的dist数组,全部初始化为无穷大,dist[i]表⽰起点到 i 结点的最短路；
• 初始化： dist[1] = 0 ，其余结点的 dist 值为⽆穷⼤，表⽰还没有找到最短路。
• 重复：每次都对所有的边进⾏⼀次松弛操作。
• 重复上述操作，直到所有边都不需要松弛操作为⽌。

最多重复多少轮松弛操作？
在最短路存在的情况下，由于⼀次松弛操作会使最短路的边数⾄少增加 1，⽽最短路的边数最多为 n - 1。因此整个算法最多执⾏轮松弛操作 n - 1 轮。故总时间复杂度为O(nm)。

P3371 【模板】单源最短路径（弱化版） - 洛谷

#include <iostream> #include <vector> using namespace std; typedef pair<int, int> PII; const int N = 1e4 + 10, M = 5e5 + 10, INF = 2147483647; int n, m, s; vector<PII> edges[M]; int dist[N]; void BF() { for (int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; bool flag; // 标记是否有结点进行过松弛操作 for (int i = 1; i <= n - 1; i++) // 最多循环 n - 1 次 { flag = false; for (int u = 1; u <= n; u++) // 每次循环都对所有结点做松弛操作 { if (dist[u] == INF) continue; for (auto& t : edges[u]) { int v = t.first, w = t.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; flag = true; } } } if (flag == false) break; } for (int i = 1; i <= n; i++) cout << dist[i] << ' '; } int main() { cin >> n >> m >> s; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({ v,w }); } BF(); return 0; }

BF 算法判断负环

P3385 【模板】负环 - 洛谷

BF 算法最多执行 n - 1 轮，如果第 n 轮仍然进行了松弛操作，说明存在负环。

bool BF() { for (int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; bool flag; // 标记是否有结点进行过松弛操作 for (int i = 1; i <= n - 1; i++) // 故意循环 n 次 { flag = false; for (int u = 1; u <= n; u++) // 每次循环都对所有结点做松弛操作 { if (dist[u] == INF) continue; for (auto& t : edges[u]) { int v = t.first, w = t.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; flag = true; } } } if (flag == false) break; } if(flag) return true; return false; }

spfa 算法

spfa 即 Shortest Path Faster Algorithm，本质是⽤队列对 BF 算法做优化。
在 BF 算法中，很多时候我们并不需要那么多⽆⽤的松弛操作：

•只有上⼀次被松弛的结点，它的出边，才有可能引起下⼀次的松弛操作；
• 因此，如果⽤队列来维护"哪些结点可能会引起松弛操作"，就能只访问必要的边了，时间复杂度就能降低。

spfa 算法流程：

准备⼯作：
◦ 创建⼀个⻓度为 n 的 dist 数组，其中 dist[i] 表⽰从起点到 i 结点的最短路；
◦ 创建⼀个⻓度为 n 的 bool 数组 st ，其中 st[i] 表⽰ i 点是否已经在队列中(现在不表示已确定最短路了）。
• 初始化：标记 dist[1] = 0 ，同时 1 ⼊队；其余结点的 dist 值为⽆穷⼤，表⽰还没有找到
最短路。
• 重复：每次拿出队头元素 u ，去掉在队列中的标记，同时对 u 所有相连的点 v 进⾏松弛操作。如果结点 v 被松弛，那就放进队列中。
• 重复上述操作，直到队列中没有结点为⽌

注意注意注意：
虽然在⼤多数情况下 spfa 跑得很快，但其最坏情况下的时间复杂度为O(NM)。将其卡到这个复杂度也是不难的，所以在没有负权边时最好使⽤ Dijkstra 算法。

#include <iostream> #include <vector> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 1e4 + 10, M = 5e5 + 10, INF = 2147483647; int n, m, s; vector<PII> edges[M]; int dist[N]; bool st[N]; void spfa() { for (int i = 0; i <= n; i++) dist[i] = INF; dist[s] = 0; queue<int> q; q.push(s); st[s] = true; while (q.size()) { int u = q.front(); q.pop(); st[u] = false; for (auto& t : edges[u]) { int v = t.first; int w = t.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!st[v]) { q.push(v); st[v] = true; } } } } for (int i = 1; i <= n; i++) cout << dist[i] << ' '; } int main() { cin >> n >> m >> s; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[u].push_back({ v,w }); } spfa(); return 0; }

spfa 算法判断负环

维护⼀个 cnt 数组记录从起点到该点所经过的边数，如果 cnt[i] >= n ，说明有负环。如何更新 cnt 数组：如果 v 点可以进行松弛操作，那么：cnt[v] = cnt[u] + 1；

P3385 【模板】负环 - 洛谷

#include <iostream> #include <vector> #include <queue> using namespace std; typedef pair<int, int> PII; const int N = 2e3 + 10, M = 3e3 + 10, INF = 2147483647; int n, m, T; vector<PII> edges[M*2]; int dist[N],cnt[N]; bool st[N]; bool spfa() { for (int i = 0; i <= n; i++) { dist[i] = INF; cnt[i] = 0; st[i] = false; } dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { int u = q.front(); q.pop(); st[u] = false; for (auto& t : edges[u]) { int v = t.first; int w = t.second; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!st[v]) { q.push(v); st[v] = true; } cnt[v] = cnt[u] + 1; if (cnt[v] >= n) return true; } } } return false; } int main() { cin >> T; while (T--) { cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; if (w >= 0) { edges[u].push_back({ v,w }); edges[v].push_back({ u,w }); } else edges[u].push_back({ v,w }); } if (spfa()) cout << "YES" << endl; else cout << "NO" << endl; for (int i = 0; i < m; i++) edges[i].clear(); } return 0; }

多源最短路 - floyd 算法

多源最短路：即一次性求出图中任意顶点间的最短路径。floyd 算法本质是动态规划，⽤来求任意两个结点之间的最短路，也称插点法。通过不断在两点之间加⼊新的点，来更新最短路。适⽤于任何图，不管有向⽆向，边权正负，但是最短路必须存在（也就是不存在负环，可以用来判断是否存在负环）。

状态表⽰： f[k][i][j] 表⽰：仅仅经过 [1, k] 这些点，结点 i ⾛到结点 j 的最短路径的⻓度。注意：仅仅经过 [1, k] 这些点，经过的顺序是任意的，并且可能不经过 [1, k] 的所有点。

状态转移⽅程：
• 第⼀种情况，不选新来的点： f[k][i][j] = f[k - 1][i][j] ；
• 第⼆种情况，选择新来的点： f[k][i][j] = f[k - 1][i][k] + f[k - 1][k][j]

空间优化：在更新 f[k] 这一层时，只会⽤到上⼀层 f[k - 1] 的状态，因此可以直接去掉第一维。

初始化：f[i][i] = 0 ； f[i][j] 为初始状态下 i 到 j 的距离，如果没有边则为⽆穷。使用邻接矩阵存图。

填表顺序：⼀定要先枚举 k ，再枚举 i 和 j 。因为我们填表的时候，需要依赖的是 k - 1 层的状态，因此 k 必须先枚举，并且从小到大枚举

B3647 【模板】Floyd - 洛谷

#include <iostream> #include <string.h> using namespace std; const int N = 110; int f[N][N],m,n; int main() { cin >> n >> m; memset(f, 0x3f, sizeof(f)); for (int i = 1; i <= n; i++) f[i][i] = 0; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; f[u][v] = f[v][u] = min(f[u][v], w); } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[k][i] + f[k][j]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { cout << f[i][j] << ' '; } cout << endl; } return 0; }

无向图的最小环问题

至少 3 个结点首尾相连的结点构成环。在所有环中边权最小的环称为最小环。把无向图的最小环的所有可能结果中，以编号最大的结点为标准分类，比如编号最大的结点如果为 3 ，也就是 1，2，3 号结点构成环，如果编号最大的结点如果为 4，也就是 4 号结点和 1，2，3 号结点中至少 2 个结点构成的环。把编号最大的结点为 3、4、5 ... n 的环都求出最小环c3、c4、c5 ... cn，再求出 c3、c4、c5 ... cn 中的最小环，结果为该无向图的最小环。

#include <iostream> using namespace std; const int N = 110; int e[N][N], f[N][N],INF = 5e8; int n, m; int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { e[i][j] = f[i][j] = INF; } } for (int i = 1; i <= n; i++) { e[i][i] = f[i][i] = 0; } for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u][v] = e[v][u] = f[u][v] = f[v][u] = min(e[u][v], w); } int ret = INF; for (int k = 1; k <= n; k++) { // 最小环，最大编号为 k for(int i = 1; i < k; i++) for (int j = i + 1; j < k; j++) ret = min(ret, f[i][j] + e[i][k] + e[k][j]); // f[i][j]、e[i][k]、e[k][j] 都可能是 INF， // 所以INF不能是0x3f3f3f3f,可能会溢出！ // 最短路径 for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]); } if (ret == INF) cout << "No solution." << endl; else cout << ret << endl; return 0; }