【代码随想录训练营第42期 Day57打卡 - 图论Part7 - Prim算法
一、Prim算法
Prim算法是一种贪心算法,用于求解加权无向图的最小生成树问题。其中,最小生成树是指一个边的子集,它连接图中的所有顶点,且边的总权重最小,并且没有形成环。
对于Prim算法的简单了解,这里推荐看看:【图-最小生成树-Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法】
二、题目与题解
题目:卡码网 53. 寻宝
题目链接
53. 寻宝(第七期模拟笔试) (kamacoder.com)
题目描述
在世界的某个区域,有一些分散的神秘岛屿,每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路,方便运输。
不同岛屿之间,路途距离不同,国王希望你可以规划建公路的方案,如何可以以最短的总公路距离将 所有岛屿联通起来(注意:这是一个无向图)。
给定一张地图,其中包括了所有的岛屿,以及它们之间的距离。以最小化公路建设长度,确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E,V代表顶点数,E代表边数 。顶点编号是从1到V。例如:V=2,一个有两个顶点,分别是1和2。
接下来共有 E 行,每行三个整数 v1,v2 和 val,v1 和 v2 为边的起点和终点,val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
输入示例
7 11 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
输出示例
6
提示信息
数据范围:
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;如下图,可见将所有的顶点都访问一遍,总距离最低是6.
题解:Prim算法
建议先看视频了解了Prim算法的实现步骤再看以下思路和步骤。
基本思路:
1.选择一个起始顶点,将其标记为已访问,并将其距离设置为0,其他顶点的距离设置为无穷大
2.创建一个循环,直到所有顶点都被访问:
初始化一个变量来记录当前最小边的权重,将其设置为无穷大。
初始化两个变量来记录最小边的两个顶点。
3.遍历所有已访问顶点,对于每个已访问顶点,遍历它的所有邻接顶点:
如果邻接顶点未被访问,并且连接这两个顶点的边的权重小于当前记录的最小边权重,则更新最小边权重和对应的两个顶点。
将找到的最小边加入到最小生成树中,并标记连接的非最小生成树顶点为已访问。 更新该顶点的所有邻接顶点到最小生成树的最短距离。
4.当所有顶点都被访问后,算法结束,此时最小生成树由记录的所有边组成。
#include <bits/stdc++.h>
using namespace std;int main()
{int v, e;int x, y, k;cin >> v >> e; // 输入顶点数v(注意范围是:1 - v)和边数evector<vector<int>> grid(v + 1, vector<int>(v + 1, 10001)); // 二维数组grid,用于存储图的邻接矩阵,初始值为10001(表示无穷大)while (e--){cin >> x >> y >> k; // 输入边的两个顶点和权值// 因为是双向图,所以两个方向都要填上grid[x][y] = k;grid[y][x] = k;}// 用于存储每个顶点到最小生成树的最短距离 -- 由于顶点数为v,这里大小设置为v+1vector<int> minDist(v + 1, 10001);// 初始化第一个顶点到最小生成树的距离为0minDist[1] = 0;// 用于标记顶点是否已经在最小生成树中vector<bool> isInTree(v + 1, false);// 我们只需要循环 n-1次,因为最小生成树有v-1条边,这样就可以把n个节点的图连在一起for (int i = 1; i < v; i++){// 选择距离最小生成树最近的顶点int cur = -1; // 当前选中的顶点 -- 最终选中的cur节点即是加入最小生成树的最近节点int minVal = INT_MAX; // 当前最小距离,初始化为无穷大for (int j = 1; j <= v; j++) // 顶点编号:1 - v{if (!isInTree[j] && minDist[j] < minVal) // 选择不在最小生成树中且距离最小的顶点{minVal = minDist[j];cur = j;}}// 最近节点(cur)加入生成树isInTree[cur] = true;// 更新非生成树节点到生成树的距离(即更新minDist数组):由于新加入了cur节点,这里只需要多考虑cur与不在最小生成树的节点的距离即可for (int j = 1; j <= v; j++){if (!isInTree[j] && grid[cur][j] < minDist[j]) // 如果顶点j不在生成树中,并且通过cur到j的距离小于当前记录的最短距离,则更新{minDist[j] = grid[cur][j];}}}int ans = 0; // 统计结果for (int i = 2; i <= v; i++) // 累加每个顶点到生成树的最短距离,注意从第二个顶点开始累加,因为第一个顶点距离为0{ans += minDist[i];}cout << ans << endl;
}
这题还可以用优先队列(堆)进行优化,这也是Prim算法最经典的使用方法:
#include <bits/stdc++.h>
using namespace std;int main()
{int v, e;cin >> v >> e; // 输入顶点数v和边数e// 使用邻接矩阵存储图的边信息,初始化为无穷大vector<vector<int>> grid(v + 1, vector<int>(v + 1, INT_MAX));// 读取边的信息for (int i = 1; i <= e; ++i){int x, y, k;cin >> x >> y >> k; // 输入边的两个顶点和权值grid[x][y] = k;grid[y][x] = k;}// 使用优先队列来存储顶点及其到最小生成树的最短距离priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;// 用于存储每个顶点到最小生成树的最短距离,初始化为无穷大vector<int> minDist(v + 1, INT_MAX);minDist[1] = 0; // 第一个顶点到最小生成树的距离为0// 标记顶点是否已经在最小生成树中vector<bool> isInTree(v + 1, false);// 将第一个顶点加入优先队列pq.push({0, 1});while (!pq.empty()){// 从优先队列中取出距离最小生成树最近的顶点int cur = pq.top().second;pq.pop();// 如果该顶点已经在最小生成树中,则跳过if (isInTree[cur])continue;// 将该顶点标记为已加入最小生成树isInTree[cur] = true;// 更新邻接顶点到最小生成树的最短距离for (int j = 1; j <= v; ++j){if (!isInTree[j] && grid[cur][j] < minDist[j]){minDist[j] = grid[cur][j];pq.push({minDist[j], j}); // 将更新后的顶点和距离加入优先队列}}}// 计算最小生成树的总权重int ans = 0;for (int i = 2; i <= v; ++i){ans += minDist[i];}cout << ans << endl; // 输出最小生成树的总权重return 0;
}
三、小结
今天的打卡比较仓促,后边有时间会对上述代码的内容以及注释进行改善,并加深自己的理解。后边继续加油!