青岛移动公司网站,用typecho做的网站,搭建小网站,电商网站平台有哪些一、算法思路
Prim 算法是用来求最小生成树的#xff0c;它的思想也有点类似于贪心——逐个将离当前集合最近的点加入到集合中#xff0c;直至发现图不连通或所有点都被加到集合中#xff0c;算法即宣告终止。它的具体做法是#xff1a; step 1#xff1a;初始时#xf…一、算法思路
Prim 算法是用来求最小生成树的它的思想也有点类似于贪心——逐个将离当前集合最近的点加入到集合中直至发现图不连通或所有点都被加到集合中算法即宣告终止。它的具体做法是 step 1初始时由当前最小生成树中的点构成的集合 S S S 为空图中剩余的点到集合的距离皆为 ∞ \infty ∞这一步可以用代码实现如下 // 假定图中共有N个点
bool st[N]; // 用bool数组st来模拟集合S若一个点i被加入集合// 则将st[i]置为true
int dist[N]; // 用dist数组来记录所有点到当前集合的最短距离
memset(dist, 0x3f, sizeof dist); // 初始时将所有点到集合的最短// 距离置为正无穷step 2接下来是 n 轮循环每轮循环的任务是找到当前离集合最近的点并将其加入集合即合并到当前的最小生成树上同时用这个点更新其他点到集合的距离当这个点加入集合后其他点到集合的最短距离有可能发生改变因为此时这个新加入的点也是集合的一部分了所以要用这个点到其他点的距离来更新其他点到集合的最短距离这一步的代码可以实现如下 // n是图中所有点的个数
for (int i 0; i n; i) // n轮循环每轮循环负责将一个点加入集合中
{// 首先要找到我们要加入的点是谁int t -1; // 先用-1来暂时表示这个点并用t来记录// 执行具体的寻找过程从1~n这n个点中将当前这一轮的t找出来for (int j 1; j n; j) // 从1到n循环n个点看哪个点符合要求if (!st[t] (t -1 || dist[j] dist[t])) // 如果这个点尚未在集合中并且// 要么找到了第一个不在集合中的点// 要么找到了离集合最短距离更小的点t j; // 就更新t的取值// 当我们找到t以后我们需要将t加入到集合中st[t] true;// 并用t到其他点的距离更新其他点到集合的最短距离for (int j 1; j n; j)dist[j] min(dist[j], g[t][j]);
}step 3如何返回最终的结果呢我们要找的是我们要返回的是最小生成树的树边权重之和以下简记为“最小生成树的长度”而这个长度是由一条条边加起来得到的。注意到每次往集合中新加入一个点就相当于当前最小生成树又多了一条边而这条边就是我们要找的众多边之一。因此只需要在每次新加入一条边的时候把新加入的边的长度累加到最终的结果中去即可这个长度即为新加入的点到集合的最短距离即为 dist[t]。 然而如果图中根本就不存在最小生成树怎么办呢如果在中途就发现了图中必然不可能存在最小生成树那能不能提前停止并返回结果呢如果可以当如何实现呢 答案是我们可以在加入每个点之前先做一个判断如果新加入的点到集合的最短距离是 ∞ \infty ∞ 这就意味着新加入的点跟集合中的点根本就不连通此时图中必不可能存在最小生成树而一旦我们发现了这样一种情况就可以提前退出循环并将当前结果报告出去其实现代码如下 // 用res来记录最终最小生成树的长度
int res 0; // 初始时res为0
for (int i 0; i n; i) // 最外层的n轮循环每轮找到一个点并加入当前集合中
{int t -1;for (int j 1; j n; j)if (!st[j] (t -1 || dist[j] dist[t]))t j;// 找到t以后这个t不一定是与当前集合连通的所以可以提前做一个判断if (i dist[t] INF) return INF; // 如果当前点到集合的最短距离为正无穷则返回正无穷最终可根据返回结果是否为正无穷来判断图中是否存在最小生成树// 如果上一步没有提前返回则说明当前点与集合是连通的那么它与集合之间将会连起一条新的边这个边是最终最小生成树的一部分要将它累加至最后的结果中if (i) res dist[t];// 注意以上两步中都有一个if(i)这个判断的目的是i0表示第一轮循环即将第一个点加入最小生成树由于第一个点到初始空集合S的距离为正无穷所以这个点不能作为“不存在最小生成树”的判断这个点到集合的距离也不能累加至最终的结果中因此正确的做法是跳过这个点即加一个if(i)的判断...// 最终返回res即可return res;
}二、Prim 算法求最小生成树的完整代码如下
#include iostream
#include cstringusing namespace std;const int N 510, M 2e5 10; // 边数设为初始值的两倍是因为无向图要加两条有向边
const int INF 0x3f3f3f3f;int n, m;
int g[N][N];
int dist[N];
bool st[N];int prim()
{memset(dist, 0x3f, sizeof dist); // 初始时设置所有点到集合的最短距离都为正无穷int res 0; // 用res记录最终最小生成树的长度for (int i 0; i n; i) // 然后开始n轮循环每轮将一个点加入当前集合中{int t -1; // 将当轮要加入的点初始化为-1for (int j 1; j n; j) // 然后从1~n这n个点中找到当前这一轮要加入的点if (!st[j] (t -1 || dist[j] dist[t]))t j;// 找到以后先做判断看图会不会不连通if (i dist[t] INF) return INF;// 如果确认当前这一轮还未发现图是不是不连通的就先将当前边累加至最终结果if (i) res dist[t];// 关键一步用t到它所有邻居的距离更新它的所有邻居到当前集合的最短距离for (int j 1; j n; j) // 遍历并找到t的所有邻居dist[j] min(dist[j], g[t][j]); // 更新邻居到当前集合的距离// 最后将当前这个点t加入到当前集合中st[t] true;}return res; // 返回图中最小生成树的长度
}int main()
{cin n m;memset(g, 0x3f, sizeof g); // 初始时设置所有边权都为正无穷// 这一步是不可省略的因为有些点之间根本就没有连接其距离为正无穷// 如果不进行这一步设置这些不连通的点之间的边将被默认初始化为0// 这显然是不对的while (m--){int a, b, w;scanf(%d%d%d, a, b, w);g[a][b] g[b][a] min(g[a][b], w);}int res prim();if (res INF) puts(impossible);else cout res endl;return 0;
}【注】以上内容参考AcWing。
