图论算法体系：并查集、生成树、排序与路径搜索全解析

从图论的基础理论入门，到深搜广搜搭建起图论的骨架。

从并查集到最小生成树，从拓扑排序到最短路径。

....

群星璀璨😉

一、并查集作用：连通性判断（两个节点是否连通）检测环（在无项图中，添加两个节点是否属于同一父节点）最小生成树（KrusKal）模版：基础应用代码语言：javascript复制简单例子；

无向图，有1~5这5个节点

1 2

2 3

3 4

求解，2与4是否连通。2与5呢？

加入1-4

是否会成环？

按照模板给出讲解顺序

// 这只是无向图中的应用，是最基础的

// 有向图会麻烦一点点压缩路径：（最基础、最常用）

代码语言：javascript复制int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好

vector father = vector (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;

}按秩合并：（大规模场景，需要性能优化时，会用到这个）（我没遇到，不知道）

代码语言：javascript复制int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好

vector father = vector (n, 0); // C++里的一种数组结构

vector rank = vector (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; 注意是 <=

}竞赛模板（路径压缩+按秩合并结合）单一的路径压缩 与 按秩合并 没有谁好谁坏，他们两者是互补的，之后结合之后，才能使并查集优化的最好。

代码语言：javascript复制#include

class UnionFind {

private:

std::vector parent;

std::vector 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算法：核心思想：从顶点出发的贪心思想，

每次循环都会连接一个 距离生成树 距离最近 的节点。

基础应用模板：三步走：

找出距离已得到生成树最近的节点。更新去重数组更新未加入生成树节点，到达生成树的最小距离。（用新加入的节点表示）代码语言：javascript复制#include

#include

#include

using namespace std;

int main() {

int v, e;

int x, y, k;

cin >> v >> e;

// 填一个默认最大值，题目描述val最大为10000

vector> grid(v + 1, vector(v + 1, 10001));

while (e--) {

cin >> x >> y >> k;

// 因为是双向图，所以两个方向都要填上

grid[x][y] = k;

grid[y][x] = k;

}

// 所有节点到最小生成树的最小距离

vector minDist(v + 1, 10001);

// 这个节点是否在树里

vector 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算法：（克鲁斯卡尔算法）

核心思想：从 “边” 开始的，贪心思想。

基础应用：代码语言：javascript复制初始数据

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数组，建立最小生成树代码语言：javascript复制#include

#include

#include

using namespace std;

// l,r为 边两边的节点，val为边的数值

struct Edge {

int l, r, val;

};

// 节点数量

int n = 10001;

// 并查集标记节点关系的数组

vector 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 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的节点，并加入结果集减去与该节点相连的入度（将该节点从图中移除）模板代码语言：javascript复制#include

#include

#include

#include

using namespace std;

int main() {

int m, n, s, t;

cin >> n >> m;

vector inDegree(n, 0); // 记录每个文件的入度

unordered_map> umap;// 记录文件依赖关系

vector result; // 记录结果

while (m--) {

// s->t，先有s才能有t

cin >> s >> t;

inDegree[t]++; // t的入度加一

umap[s].push_back(t); // 记录s指向哪些文件

}

queue 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 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朴素版：模板：三部走：

选源点到那个节点近，且该节点未被访问过标记该节点为已访问过更新非访问节点，到源点的距离代码语言：javascript复制#include

#include

#include

using namespace std;

int main() {

int n, m, p1, p2, val;

cin >> n >> m;

vector> grid(n + 1, vector(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 minDist(n + 1, INT_MAX);

// 记录顶点是否被访问过

std::vector 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挺像，就是以边为中心的贪心思想。

代码语言：javascript复制#include

#include

#include

#include

#include

using namespace std;

// 小顶堆

class mycomparison {

public:

bool operator()(const pair& lhs, const pair& 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> 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 minDist(n + 1, INT_MAX);

// 记录顶点是否被访问过

std::vector visited(n + 1, false);

// 优先队列中存放 pair<节点，源点到该节点的权值>

priority_queue, vector>, mycomparison> pq;

// 初始化队列，源点到源点的距离为0，所以初始为0

pq.push(pair(start, 0));

minDist[start] = 0; // 起始点到自身的距离为0

while (!pq.empty()) {

// 1. 第一步，选源点到哪个节点近且该节点未被访问过 （通过优先级队列来实现）

// <节点， 源点到该节点的距离>

pair 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(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基础应用：代码语言：javascript复制A → B：3（花费为 3）

A → C：5（花费为 5）

B → C：-1（花费 -1，相当于补贴了钱）

B → D：3（花费为 3）

C → D：4（花费为 4）模板：代码语言：javascript复制#include

#include

#include

#include

using namespace std;

int main() {

int n, m, p1, p2, val;

cin >> n >> m;

vector> 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 minDist(n + 1 , INT_MAX);

minDist[start] = 0;

for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次

for (vector &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算法。以“边”为起始的贪心算法

基础应用：代码语言：javascript复制A → B：3（花费为 3）

A → C：5（花费为 5）

B → C：-1（花费 -1，相当于补贴了钱）

B → D：3（花费为 3）

C → D：4（花费为 4）模板：代码语言：javascript复制#include

#include

#include

#include

#include

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> grid(n + 1);

vector 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 minDist(n + 1 , INT_MAX);

minDist[start] = 0;

queue 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...结果都不会在变。

若出现负权回路！不论循环多少次，内容一直会改变。

代码语言：javascript复制#include

#include

#include

#include

using namespace std;

int main() {

int n, m, p1, p2, val;

cin >> n >> m;

vector> 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 minDist(n + 1 , INT_MAX);

minDist[start] = 0;

bool flag = false;

for (int i = 1; i <= n; i++) { // 这里我们松弛n次，最后一次判断负权回路

for (vector &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次，就会说明出现了负权回路。

代码语言：javascript复制#include

#include

#include

#include

#include

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> 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 minDist(n + 1 , INT_MAX);

minDist[start] = 0;

queue que;

que.push(start); // 队列里放入起点

vector 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、朴素版：代码语言：javascript复制// 版本二

#include

#include

#include

#include

using namespace std;

int main() {

int src, dst,k ,p1, p2, val ,m , n;

cin >> n >> m;

vector> grid;

for(int i = 0; i < m; i++){

cin >> p1 >> p2 >> val;

grid.push_back({p1, p2, val});

}

cin >> src >> dst >> k;

vector minDist(n + 1 , INT_MAX);

minDist[src] = 0;

vector minDist_copy(n + 1); // 用来记录上一次遍历的结果

for (int i = 1; i <= k + 1; i++) {

minDist_copy = minDist; // 获取上一次计算的结果

for (vector &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：代码语言：javascript复制 // 将所有边保存起来

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 minDist(n + 1 , INT_MAX);

vector minDist_copy(n + 1); // 用来记录每一次遍历的结果

minDist[start] = 0;

queue 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)）

模板：代码语言：javascript复制#include

#include

using namespace std;

int main() {

int n, m, p1, p2, val;

cin >> n >> m;

vector> grid(n + 1, vector(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广搜的基础之上。

用以下这道题目举例子：

模板： 代码语言：javascript复制#include

#include

#include

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 pq;

pq.push(k);

knight node,cur;

while(!pq.empty()){

node = pq.top(); pq.pop();

if(node.m1==b1&&node.m2==b2){

cout<

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<

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、图论总结篇