图论算法体系：并查集、生成树、排序与路径搜索全解析
图论算法体系：并查集、生成树、排序与路径搜索全解析
十二.
发布于 2025-10-22 15:25:47
发布于 2025-10-22 15:25:47
从图论的基础理论入门，到深搜广搜搭建起图论的骨架。 从并查集到最小生成树，从拓扑排序到最短路径。 .... 群星璀璨😉
一、并查集
作用：
- 连通性判断（两个节点是否连通）
- 检测环（在无项图中，添加两个节点是否属于同一父节点）
- 最小生成树（KrusKal）
模版：
基础应用
简单例子；
无向图，有1~5这5个节点
1 2
2 3
3 4
求解，2与4是否连通。2与5呢？
加入1-4
是否会成环？
按照模板给出讲解顺序
// 这只是无向图中的应用，是最基础的
// 有向图会麻烦一点点
压缩路径：
（最基础、最常用）
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集里寻根的过程
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
father[v] = u;
}按秩合并：
（大规模场景，需要性能优化时，会用到这个）（我没遇到，不知道）
int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构
vector<int> rank = vector<int> (n, 1); // 初始每棵树的高度都为1
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
rank[i] = 1; // 也可以不写
}
}
// 并查集里寻根的过程
int find(int u) {
return u == father[u] ? u : find(father[u]);// 注意这里不做路径压缩
}
// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (rank[u] <= rank[v]) father[u] = v; // rank小的树合入到rank大的树
else father[v] = u;
if (rank[u] == rank[v] && u != v) rank[v]++; // 如果两棵树高度相同，则v的高度+1，因为上面 if (rank[u] <= rank[v]) father[u] = v; 注意是 <=
}竞赛模板（路径压缩+按秩合并结合）
单一的路径压缩 与 按秩合并 没有谁好谁坏，他们两者是互补的，之后结合之后，才能使并查集优化的最好。
#include <vector>
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> rank; // 秩（树高度的上界）
int count; // 连通分量个数
public:
UnionFind(int n) : count(n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; ++i) {
parent[i] = i;
}
}
int find(int x) {
// 路径压缩：在查找过程中将节点直接连接到根节点
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
// 按秩合并：将秩较小的树合并到秩较大的树
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rank[rootX]++; // 秩相同时，合并后秩增加1
}
count--;
}
bool connected(int x, int y) {
return find(x) == find(y);
}
int getCount() {
return count;
}
};使用说明：
- 初始化：创建大小为
n的并查集，每个元素初始独立成集合 - find(x)：查找
x的根节点，同时进行路径压缩 - unite(x, y)：合并
x和y所在的集合，按秩保持树结构平衡 - connected(x, y)：判断
x和y是否属于同一集合 - getCount()：返回当前连通分量（集合）的数量
特点：
- ⚡ 高效：近似常数时间复杂度（阿克曼函数的反函数）
- 📦 紧凑：仅使用两个数组存储状态
- 🏆 竞赛友好：直接用于需要并查集的算法题目
典型应用场景：
- 最小生成树（Kruskal算法）
- 动态连通性问题
- 图的连通分量统计
- 最近公共祖先（LCA）等
使用时，只需要初始化一个类，然后调用，就可以了
二、最小生成树
基础定义：
给一个无向连通图，找到一个子图，满足：
- 包含所有顶点（N个顶点）
- 有N-1条边
- 边权值最小
（举例详细解释一下） prime是以点为基础，所以更适合稠密图（O(N^2)） Kruskal以边为基础，更适合稀疏图 (O(nlogn)) （一般题目会这样出题：有多个城市之间埔公路(A、B、C、D)，求如何才能用最少的原材料，让所有城市之间连通？）
Prim算法：
核心思想：
从顶点出发的贪心思想， 每次循环都会连接一个 距离生成树 距离最近 的节点。
基础应用
模板：
三步走：
- 找出距离已得到生成树最近的节点。
- 更新去重数组
- 更新未加入生成树节点，到达生成树的最小距离。（用新加入的节点表示）
#include<iostream>
#include<vector>
#include <climits>
using namespace std;
int main() {
int v, e;
int x, y, k;
cin >> v >> e;
// 填一个默认最大值，题目描述val最大为10000
vector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001));
while (e--) {
cin >> x >> y >> k;
// 因为是双向图，所以两个方向都要填上
grid[x][y] = k;
grid[y][x] = k;
}
// 所有节点到最小生成树的最小距离
vector<int> minDist(v + 1, 10001);
// 这个节点是否在树里
vector<bool> isInTree(v + 1, false);
// 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
for (int i = 1; i < v; i++) {
// 1、prim三部曲，第一步：选距离生成树最近节点
int cur = -1; // 选中哪个节点 加入最小生成树
int minVal = INT_MAX;
for (int j = 1; j <= v; j++) { // 1 - v，顶点编号，这里下标从1开始
// 选取最小生成树节点的条件：
// （1）不在最小生成树里
// （2）距离最小生成树最近的节点
if (!isInTree[j] && minDist[j] < minVal) {
minVal = minDist[j];
cur = j;
}
}
// 2、prim三部曲，第二步：最近节点（cur）加入生成树
isInTree[cur] = true;
// 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
// cur节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即minDist数组）需要更新一下
// 由于cur节点是新加入到最小生成树，那么只需要关心与 cur 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢
for (int j = 1; j <= v; j++) {
// 更新的条件：
// （1）节点是 非生成树里的节点
// （2）与cur相连的某节点的权值 比 该某节点距离最小生成树的距离小
// 很多录友看到自己 就想不明白什么意思，其实就是 cur 是新加入 最小生成树的节点，那么 所有非生成树的节点距离生成树节点的最近距离 由于 cur的新加入，需要更新一下数据了
if (!isInTree[j] && grid[cur][j] < minDist[j]) {
minDist[j] = grid[cur][j];
}
}
}
// 统计结果
int result = 0;
for (int i = 2; i <= v; i++) { // 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边
result += minDist[i];
}
cout << result << endl;
}Kruskal算法：
（克鲁斯卡尔算法）
核心思想：
从 “边” 开始的，贪心思想。
基础应用：
初始数据
7 11 // 7个节点、11条边
1 2 1 // 顶点1与顶点2相连、权值为1
1 3 1
1 5 2
2 6 1
2 4 2
2 3 2
3 4 1
4 5 1
5 6 2
5 7 1
6 7 1
求解最小生成树，权值最小为多少。可以转化为：
（有多个城市之间埔公路，求如何才能用最少的原材料，让所有城市之间连通？）
// 排序过后的
1 2 1
1 3 1
2 6 1
3 4 1
4 5 1
6 7 1
5 7 1
2 3 2
1 5 2
2 4 2
5 6 2模板：
重点步骤：
- 储存每条边，并按照权值大小按照升序排序，放在edges数组中
- 建立并查集模板
- 通过edges数组，建立最小生成树
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// l,r为 边两边的节点，val为边的数值
struct Edge {
int l, r, val;
};
// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的，n要大一些
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集的查找操作
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}
// 并查集的加入集合
void join(int u, int v) {
u = find(u); // 寻找u的根
v = find(v); // 寻找v的根
if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
father[v] = u;
}
int main() {
int v, e;
int v1, v2, val;
vector<Edge> edges;
int result_val = 0;
cin >> v >> e;
while (e--) {
cin >> v1 >> v2 >> val;
edges.push_back({v1, v2, val});
}
// 执行Kruskal算法
// 按边的权值对边进行从小到大排序
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.val < b.val;
});
// 并查集初始化
init();
// 从头开始遍历边
for (Edge edge : edges) {
// 并查集，搜出两个节点的祖先
int x = find(edge.l);
int y = find(edge.r);
// 如果祖先不同，则不在同一个集合
if (x != y) {
result_val += edge.val; // 这条边可以作为生成树的边
join(x, y); // 两个节点加入到同一个集合
}
}
cout << result_val << endl;
return 0;
}三、拓扑排序：
作用：
拓扑排序是将，有向图转化为线性关系。
（先上A课，才能上B课，上了A课才能上C课，先上C课才能上B课，上了B课才能上D课）
求上课顺序应该如何排序（有多种排序方式）
最常用的方式是卡恩算法(BFS)（另一种是DFS回溯法）
Kahn算法
两步走：
- 找到入度为0的节点，并加入结果集
- 减去与该节点相连的入度（将该节点从图中移除）
模板
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;
int main() {
int m, n, s, t;
cin >> n >> m;
vector<int> inDegree(n, 0); // 记录每个文件的入度
unordered_map<int, vector<int>> umap;// 记录文件依赖关系
vector<int> result; // 记录结果
while (m--) {
// s->t，先有s才能有t
cin >> s >> t;
inDegree[t]++; // t的入度加一
umap[s].push_back(t); // 记录s指向哪些文件
}
queue<int> que;
for (int i = 0; i < n; i++) {
// 入度为0的文件，可以作为开头，先加入队列
if (inDegree[i] == 0) que.push(i);
//cout << inDegree[i] << endl;
}
// int count = 0;
while (que.size()) {
int cur = que.front(); // 当前选中的文件
que.pop();
//count++;
result.push_back(cur);
vector<int> files = umap[cur]; //获取该文件指向的文件
if (files.size()) { // cur有后续文件
for (int i = 0; i < files.size(); i++) {
inDegree[files[i]] --; // cur的指向的文件入度-1
if(inDegree[files[i]] == 0) que.push(files[i]);
}
}
}
if (result.size() == n) {
for (int i = 0; i < n - 1; i++) cout << result[i] << " ";
cout << result[n - 1];
} else cout << -1 << endl;
}四、最短路径算法
基础定义：
从起点到终点的最短路径。 举一个形象一点的例子：导航地图，你到目的地的推荐路径。
Dijkstra
(迪杰斯特拉算法)--同样是以 “点” 为起始的贪心思想，方法与prim大同小异。
基础应用：
举例：从1到各个节点之间最短距离。（所有权值，必须是正值）
dijkstra朴素版：
模板：
三部走：
- 选源点到那个节点近，且该节点未被访问过
- 标记该节点为已访问过
- 更新非访问节点，到源点的距离
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1][p2] = val;
}
int start = 1;
int end = n;
// 存储从源点到每个节点的最短距离
std::vector<int> minDist(n + 1, INT_MAX);
// 记录顶点是否被访问过
std::vector<bool> visited(n + 1, false);
minDist[start] = 0; // 起始点到自身的距离为0
for (int i = 1; i <= n; i++) { // 遍历所有节点
int minVal = INT_MAX;
int cur = 1;
// 1、选距离源点最近且未访问过的节点
for (int v = 1; v <= n; ++v) {
if (!visited[v] && minDist[v] < minVal) {
minVal = minDist[v];
cur = v;
}
}
visited[cur] = true; // 2、标记该节点已被访问
// 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (int v = 1; v <= n; v++) {
if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
minDist[v] = minDist[cur] + grid[cur][v];
}
}
}
if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径
}dijkstra堆优化法：
模板：
堆优化法，其实挺好实现的，跟Kruskal挺像，就是以边为中心的贪心思想。
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;
// 小顶堆
class mycomparison {
public:
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second;
}
};
// 定义一个结构体来表示带权重的边
struct Edge {
int to; // 邻接顶点
int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<list<Edge>> grid(n + 1);
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点
// 存储从源点到每个节点的最短距离
std::vector<int> minDist(n + 1, INT_MAX);
// 记录顶点是否被访问过
std::vector<bool> visited(n + 1, false);
// 优先队列中存放 pair<节点，源点到该节点的权值>
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;
// 初始化队列，源点到源点的距离为0，所以初始为0
pq.push(pair<int, int>(start, 0));
minDist[start] = 0; // 起始点到自身的距离为0
while (!pq.empty()) {
// 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）
// <节点， 源点到该节点的距离>
pair<int, int> cur = pq.top(); pq.pop();
if (visited[cur.first]) continue;
// 2. 第二步，该最近节点被标记访问过
visited[cur.first] = true;
// 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）
for (Edge edge : grid[cur.first]) { // 遍历 cur指向的节点，cur指向的节点为 edge
// cur指向的节点edge.to，这条边的权值为 edge.val
if (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDist
minDist[edge.to] = minDist[cur.first] + edge.val;
pq.push(pair<int, int>(edge.to, minDist[edge.to]));
}
}
}
if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径
}为什么不能有负值：
可以自己模拟一遍
Bellman ford算法
（贝尔曼-福特算法）- 解决权值为负的问题
核心思想：
贝尔曼-福特算法，的核心是松弛操作。 尝试通过中间节点缩短路径的，就是松弛操作。 如：点之间的最短距离，点A到点B的最短距离是3，点B到点C的最短距离是-2，点A到点C之间的最短距离是2； 点A->点C的最短距离（A先到B，再到C）（3+(-2))=1；减半减半的呢
Bellman_ford
基础应用：
A → B：3（花费为 3）
A → C：5（花费为 5）
B → C：-1（花费 -1，相当于补贴了钱）
B → D：3（花费为 3）
C → D：4（花费为 4）
模板：
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<vector<int>> grid;
// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid.push_back({p1, p2, val});
}
int start = 1; // 起点
int end = n; // 终点
vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
for (vector<int> &side : grid) { // 每一次松弛，都是对所有边进行松弛
int from = side[0]; // 边的出发点
int to = side[1]; // 边的到达点
int price = side[2]; // 边的权值
// 松弛操作
// minDist[from] != INT_MAX 防止从未计算过的节点出发
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
}
}
}
if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径
}Bellman_ford优先队列（SPFA）
其实，SPFA就是对应kruskal算法。以“边”为起始的贪心算法
基础应用：
A → B：3（花费为 3）
A → C：5（花费为 5）
B → C：-1（花费 -1，相当于补贴了钱）
B → D：3（花费为 3）
C → D：4（花费为 4）模板：
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;
struct Edge { //邻接表
int to; // 链接的节点
int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<list<Edge>> grid(n + 1);
vector<bool> isInQueue(n + 1); // 加入优化，已经在队里里的元素不用重复添加
// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点
vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
queue<int> que;
que.push(start);
while (!que.empty()) {
int node = que.front(); que.pop();
isInQueue[node] = false; // 从队列里取出的时候，要取消标记，我们只保证已经在队列里的元素不用重复加入
for (Edge edge : grid[node]) {
int from = node;
int to = edge.to;
int value = edge.val;
if (minDist[to] > minDist[from] + value) { // 开始松弛
minDist[to] = minDist[from] + value;
if (isInQueue[to] == false) { // 已经在队列里的元素不用重复添加
que.push(to);
isInQueue[to] = true;
}
}
}
}
if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径
}Bellman_ford判断负权回路
基础应用：
图中，存在回路，并且回路的值为负值
模板：
1、朴素版
朴素版，其实是最好理解的！ 没有负权回路时会循环n-1次，之后n、n+1、n+2...结果都不会在变。 若出现负权回路！不论循环多少次，内容一直会改变。
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<vector<int>> grid;
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid.push_back({p1, p2, val});
}
int start = 1; // 起点
int end = n; // 终点
vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
bool flag = false;
for (int i = 1; i <= n; i++) { // 这里我们松弛n次，最后一次判断负权回路
for (vector<int> &side : grid) {
int from = side[0];
int to = side[1];
int price = side[2];
if (i < n) {
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price;
} else { // 多加一次松弛判断负权回路
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) flag = true;
}
}
}
if (flag) cout << "circle" << endl;
else if (minDist[end] == INT_MAX) {
cout << "unconnected" << endl;
} else {
cout << minDist[end] << endl;
}
}2、SPFA
若要用优先队列解决的话，可以根据他的一个性质，每个节点最多被松弛n-1次。 （也就是做n-1次，中间节点） 一点超过n-1次，就会说明出现了负权回路。
#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <climits>
using namespace std;
struct Edge { //邻接表
int to; // 链接的节点
int val; // 边的权重
Edge(int t, int w): to(t), val(w) {} // 构造函数
};
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<list<Edge>> grid(n + 1); // 邻接表
// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点
vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
queue<int> que;
que.push(start); // 队列里放入起点
vector<int> count(n+1, 0); // 记录节点加入队列几次
count[start]++;
bool flag = false;
while (!que.empty()) {
int node = que.front(); que.pop();
for (Edge edge : grid[node]) {
int from = node;
int to = edge.to;
int value = edge.val;
if (minDist[to] > minDist[from] + value) { // 开始松弛
minDist[to] = minDist[from] + value;
que.push(to);
count[to]++;
if (count[to] == n) {// 如果加入队列次数超过 n-1次 就说明该图与负权回路
flag = true;
while (!que.empty()) que.pop();
break;
}
}
}
}
if (flag) cout << "circle" << endl;
else if (minDist[end] == INT_MAX) {
cout << "unconnected" << endl;
} else {
cout << minDist[end] << endl;
}
}Bellman_ford之单源最短路
基础应用：
共有1~n各城市，要求城市1->城市n，最多经历k个城市。
模板：
其实挺容易理解的，只要创建两个minDist，复用上一个minDist就行。 在这个前提下，只需要k次，就能求出所有（1~k）的城市。
1、朴素版：
// 版本二
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;
int main() {
int src, dst,k ,p1, p2, val ,m , n;
cin >> n >> m;
vector<vector<int>> grid;
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid.push_back({p1, p2, val});
}
cin >> src >> dst >> k;
vector<int> minDist(n + 1 , INT_MAX);
minDist[src] = 0;
vector<int> minDist_copy(n + 1); // 用来记录上一次遍历的结果
for (int i = 1; i <= k + 1; i++) {
minDist_copy = minDist; // 获取上一次计算的结果
for (vector<int> &side : grid) {
int from = side[0];
int to = side[1];
int price = side[2];
// 注意使用 minDist_copy 来计算 minDist
if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + price) {
minDist[to] = minDist_copy[from] + price;
}
}
}
if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点
else cout << minDist[dst] << endl; // 到达终点最短路径
}2、SPFA：
// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2，权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start, end, k;
cin >> start >> end >> k;
k++;
vector<int> minDist(n + 1 , INT_MAX);
vector<int> minDist_copy(n + 1); // 用来记录每一次遍历的结果
minDist[start] = 0;
queue<int> que;
que.push(start); // 队列里放入起点
int que_size;
while (k-- && !que.empty()) {
minDist_copy = minDist; // 获取上一次计算的结果
que_size = que.size(); // 记录上次入队列的节点个数
while (que_size--) { // 上一轮松弛入队列的节点，这次对应的边都要做松弛
int node = que.front(); que.pop();
for (Edge edge : grid[node]) {
int from = node;
int to = edge.to;
int price = edge.val;
if (minDist[to] > minDist_copy[from] + price) {
minDist[to] = minDist_copy[from] + price;
que.push(to);
}
}
}
}
if (minDist[end] == INT_MAX) cout << "unreachable" << endl;
else cout << minDist[end] << endl;
}Floyed算法
基础应用：
假设你有一张包含多个城市的交通图，想一次性知道 任意两个城市之间的最短路线（比如全国城市间的多对多导航）。Floyd 算法专门解决这类 全源最短路径 问题，即求出图中所有点对之间的最短路径。
核心思想:
尝试让每个节点做为一个 “中转节点” 。看能不能缩短两点之间的距离。
适合求多元最短路径，n<200最佳（O(n^3)）
模板：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, m, p1, p2, val;
cin >> n >> m;
vector<vector<int>> grid(n + 1, vector<int>(n + 1, 10005)); // 因为边的最大距离是10^4
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
grid[p1][p2] = val;
grid[p2][p1] = val; // 注意这里是双向图
}
// 开始 floyd
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
grid[i][j] = min(grid[i][j], grid[i][k] + grid[k][j]);
}
}
}
// 输出结果
int z, start, end;
cin >> z;
while (z--) {
cin >> start >> end;
if (grid[start][end] == 10005) cout << -1 << endl;
else cout << grid[start][end] << endl;
}
}A*算法
Astar的核心，在于 启发式函数。 他是建立在BFS广搜的基础之上。
用以下这道题目举例子：
模板：
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
// 本题有好几个地方需要注意
// 第一，创建结构体，并与优先队列相结合
// 第二，创建二维数组用于去重，并记录走了多少步
// 第三，启发式搜索的权值，用欧拉函数计算，且欧拉函数
//（起点到该点经过的距离）+（该点的距离到终点的距离）
// 其中从起点到该点的距离，容易被用错。是依次经过的距离，不是直线距离。
int a1,a2,b1,b2;
struct knight{
int m1,m2;
int g,h,f;
bool operator<(const knight& k)const{ // 调节为小根堆
return f>k.f;
}
};
int visited[1005][1005];
int dir[8][2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};
int get_squeeze(int m1,int m2,int b1,int b2){
return (b1-m1)*(b1-m1)+(b2-m2)*(b2-m2);
}
void astar(knight k){
priority_queue<knight> pq;
pq.push(k);
knight node,cur;
while(!pq.empty()){
node = pq.top(); pq.pop();
if(node.m1==b1&&node.m2==b2){
cout<<visited[node.m1][node.m2]<<endl;
break;
}
for(int i=0; i<8; ++i){
cur = node;
cur.m1+=dir[i][0];
cur.m2+=dir[i][1];
if(cur.m1<1||cur.m1>1000||cur.m2<1||cur.m2>1000) continue;
if(visited[cur.m1][cur.m2]) continue;
visited[cur.m1][cur.m2]=visited[node.m1][node.m2]+1; // 需要在原来的基础上进行操作
cur.g=node.g+5; // 1*1+2*2=5
cur.h=get_squeeze(cur.m1,cur.m2,b1,b2);
cur.f=cur.h+cur.g;
pq.push(cur);
}
}
}
int main(){
int t;
cin>>t;
while(t--){
cin>>a1>>a2>>b1>>b2;
if(a1==b1&&a2==b2){ // 直接排除意外情况
cout<<0<<endl;
continue;
}
memset(visited,0,sizeof visited);
knight k;
k.m1 = a1;
k.m2 = a2;
k.g = 0;
k.h = get_squeeze(k.m1,k.m2,b1,b2);
astar(k);
}
return 0;
}借鉴博客：
1、图论总结篇
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2025-09-11，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
