当前位置：首页 > news >正文

代码随想录算法训练day63---图论系列7《prim算法kruskal算法》

news 来源：原创 2025/9/16 13:48:27

代码随想录算法训练

—day63

文章目录

代码随想录算法训练
前言
一、53. 寻宝—prim算法
- 打印出来最小生成树的每条边
二、53. 寻宝—kruskal算法
- 打印出来最小生成树的每条边
总结

前言

今天是算法营的第63天，希望自己能够坚持下来！
今天继续图论part！今日任务：
● prim算法
●kruskal算法

一、53. 寻宝—prim算法

卡码网题目链接
文章讲解

思路：
本题是最小生成树的模板题，最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。
图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。
如何选择这n-1条边就是最小生成树算法的任务所在。

prim算法核心就是三步，

第一步，选距离生成树最近节点
第二步，最近节点加入生成树
第三步，更新非生成树节点到生成树的距离（即更新minDist数组）

prim算法一共需要三个数组，一个用来存放节点，一个用来存放非生成树节点到生成树节点的距离，还有一个用来记录已经在生成树中的节点。
vector<vector> grid，vector minDist，vector isInTree

代码流程：
遍历n-1条边，遍历所有节点->根据minDist数组找到最近的节点，将节点加入生成树（标记isInTree为true）->更新minDist 最后minDist的就是到达所有节点的最小距离，累加得出结果（第一个节点不需要，只需要n-1条边）

时间复杂度:O（n2）（两个for循环）

代码如下：

#include<iostream>
#include<vector>
#include<climits>
using namespace std;int main() {int v, e;int x, y, k;cin >> v >> e;//填一个默认最大值，题目描述val最大为10000vector<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个节点，只需要循环n-1次，建立n-1条边for (int i = 1; i < v; i++) {//1.选距离生成树最近节点int cur = -1; //记录找到最近的节点int minVal = INT_MAX;for (int j = 1; j <= v; j++) { //遍历顶点，1-v，顶点编号从1开始//非生成树节点并且距离比最小值小if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}//2.将最近节点cur加入生成树isInTree[cur] = true;//3.更新minDist数组//只需关心新加入的cur与剩余非生成树节点的距离是否比原来的小for (int j = 1; j <= v; j++) {//非生成树节点，并且新加入的cur到该节点的距离比之前记录的小if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];}}}int result = 0;//不计第一个顶点，因为统计的是边的权值，v个节点有v-1条边for (int i = 2; i <= v; i++) {result += minDist[i];}cout << result << endl;  
}

打印出来最小生成树的每条边

其实就是记录两个节点就可以，两个节点连成一条边。
使用一维数组就可以记录。parent[节点编号] = 节点编号，这样就把一条边记录下来了。（当然如果节点编号非常大，可以考虑使用map）
使用一维数组记录是有向边，不过我们这里不需要记录方向，所以只关注两条边是连接的就行。
parent数组初始化代码：

vector<int> parent(v + 1, -1);

在prim三部曲中的第三步，更新parent数组，代码如下：

for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 记录最小生成树的边 （注意数组指向的顺序很重要）}
}

这里需要注意是parent[j] = cur;不是parent[cur] = j；
因为对于cur这个节点，是可以通向多条边的，那么就是多个j对应同一个cur。

以下是完整代码：

#include<iostream>
#include<vector>
#include <climits>using namespace std;
int main() {int v, e;int x, y, k;cin >> v >> e;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);//加上初始化vector<int> parent(v + 1, -1);for (int i = 1; i < v; i++) {int cur = -1;int minVal = INT_MAX;for (int j = 1; j <= v; j++) {if (!isInTree[j] &&  minDist[j] < minVal) {minVal = minDist[j];cur = j;}}isInTree[cur] = true;for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 记录边}}}// 输出 最小生成树边的链接情况for (int i = 1; i <= v; i++) {cout << i << "->" << parent[i] << endl;}
}

代码输出：

1->-1
2->1
3->1
4->3
5->4
6->2
7->5

二、53. 寻宝—kruskal算法

卡码网题目链接
文章讲解

prim 算法是维护节点的集合，而 Kruskal 是维护边的集合。
kruscal的思路：
1.将边按权值从小到大排序
2.将权值最小，且不构成环的边加入到集合中（使用并查集）

代码如下：

#include<iostream>
#include<vector>
#include <algorithm>using namespace std;int n = 10001;
vector<int> father(n + 1, 0);struct Edge {int l, r, val;
};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]);
}bool isSame(int u, int v) {u = find(u);v = find(v);return u == v;
}void join(int u, int v) {u = find(u);v = find(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;}

打印出来最小生成树的每条边

因为 Kruskal 本来就是直接操作边，只需要找到在哪里把生成树的边保存下来就可以了。
当判断两个节点不在同一个集合的时候，这两个节点的边就加入到最小生成树，所以添加边的操作在这里：

vector<Edge> result; // 存储最小生成树的边
// 如果祖先不同，则不在同一个集合
if (x != y) {result.push_back(edge); // 记录最小生成树的边result_val += edge.val; // 这条边可以作为生成树的边join(x, y); // 两个节点加入到同一个集合
}

总结

prim算法：
1.需要三个数组，一个存放节点和权值vector<vector> grid，一个存放非生成树节点到生成树的最小距离vectorminDist，一个存放节点是否成为生成树节点vectorisInTree。
2.循环n-1次，遍历节点，找到是非生成树节点并且距离最小，加入到生成树节点中（isInTree标记为true）
3.遍历节点，更新minDist
kruskal算法：
1.自定义结构体，Edge（v1,v2,val）,用vectoredges存放边
2.遍历每条边，分别找到边的两个节点的根，判断如果不构成环也就是不同根（使用并查集），则两节点加入到集合（这条边加入到生成树中了），同时累加权值

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。如果一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

Prim 算法时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。
Kruskal算法时间复杂度为 nlogn，其中n 为边的数量，适用稀疏图。

明天继续加油！