首页 / 算法 / 贪心法之prim算法和Kruskal算法
贪心法之prim算法和Kruskal算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了贪心法之prim算法和Kruskal算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3630字,纯文字阅读大概需要6分钟。
内容图文
![贪心法之prim算法和Kruskal算法](/upload/InfoBanner/zyjiaocheng/622/dbbde90b26e04c89bd37f8a843633bd2.jpg)
最小生成树
性质:n个节点生成的最小生成树有n-1条边 & 最小生成树里多加一条边能生成含该边的一个环
构造方法:Prim算法 & Kruskal算法
一、Prim算法:逐个点连通的方式构造最小生成树(时间复杂度O(n*n),适合稠密图)
稀疏图&稠密图:有很少条边或弧(边的条数|E|远小于|V|²)的图称为稀疏图(sparse graph),反之边的条数|E|接近|V|²,称为稠密图(dense graph)。
Prim算法是从一个点开始,在给的无向图中寻找这个点所连接的权值最小的边,并在树中连接这条边,再寻找树中节点在无向图连接的权值最小的边,找到之后要判断这条边是否会构成一个环,最小生成树中是不能出现环的。
下图的例子:①从点1开始,权值最小的边是(1,3),权值为1,连接;②点1和点3在原始无向图中权值最小的边是(3,6),权值为4,连接;③从点1、点3和点6中权值最小的边是(6,4),权值为2连接;④在点1、3、6、4中权值最小的边是(4,1)和(3,2),权值都为5,但是(4,1)连接后会构成环,所以不能连接(4,1);⑤再找点1、3、6、4、2中权值最小的边,连接(2,5),完成最小生成树的构造。
代码如下:
![贪心法之prim算法和Kruskal算法 - 文章图片](/upload/getfiles/0001/2021/5/1/20210501014445970.jpg)
![贪心法之prim算法和Kruskal算法 - 文章图片](/upload/getfiles/0001/2021/5/1/20210501014446065.jpg)
#include<iostream> #include<cstring> using namespace std; int n,m; int map[101][101]; void prim() //最小生成树 prim算法 { cout<<"prim:"<<endl; int lowcost[101]; //lowcost[i]存树中点到i点的边的权值最小为多少 => 为多少? int closest[101]; //closest[i]存放树中哪个点到i点的边的权值最小 => 是哪个? bool s[101]; s[1] = true; //选择1为树顶 int i,j,k; for(i=2;i<=n;i++) //初始化lowcost和s { lowcost[i] = map[1][i]; s[i] = false; closest[i] = 1; } int min; for(i=1;i<n;i++) //最小生成树只有n-1条边 { min = 100000; k = 1; for(j=2;j<=n;j++) //找最小边 { if((lowcost[j]<min)&&(!s[j])) { min = lowcost[j]; k = j; } } cout<<closest[k]<<","<<k<<":"<<min<<endl; s[k] = true; for(j=2;j<=n;j++) { if((map[k][j]<lowcost[j])&&(!s[j])) //如果新的结点到j的边比原来的结点到j的边小,就用新结点替换掉原结点 { lowcost[j] = map[k][j]; closest[j] = k; } } } } int main() { cin>>n>>m; int i,a,b,tem; memset(map,0x3f,sizeof(map)); //memset要用0x3f for(i=1;i<=m;i++) { cin>>a>>b; cin>>tem; map[a][b] = tem; map[b][a] = tem; } prim(); return 0; }View Code
运行结果:
二、Kruskal算法:按权值递增的顺序选择合适的边构造最小生成树(时间复杂度O(eloge),适合稀疏图)
PS:有很少条边或弧(边的条数|E|远小于|V|²)的图称为稀疏图(sparse graph),反之边的条数|E|接近|V|²,称为稠密图(dense graph)。
先找出权值最小的边,将两个点连接,再找权值第二小的边,判断连接这两个点是否会形成环,如果不会就连接,如果会就不连接。
下图的例子:①权值最小边(1,3)连接;②剩下的权值最小边(4,6),判断不会形成环,连接;③剩下的权值最小边(2,5),判断不会形成环,连接;④剩下的权值最小边(3,6),判断不会形成环,连接;⑤剩下的权值最小边只有(3,2)不会形成环,连接。
代码实现:
![贪心法之prim算法和Kruskal算法 - 文章图片](/upload/getfiles/0001/2021/5/1/20210501014445970.jpg)
![贪心法之prim算法和Kruskal算法 - 文章图片](/upload/getfiles/0001/2021/5/1/20210501014446065.jpg)
#include<iostream> #include<cstring> using namespace std; int pre[101]; int u[101],v[101],edge[101]; //u,v分别为两个点,edge为两个点之间的边 int m,n; int find(int x) { int root = x; while(pre[root]!=root) root = pre[root]; //路径压缩 int i,j; i = x; while(pre[i]!=root) { j = i; i = pre[i]; pre[j] = root; } return root; } void kruskal() //最小生成树,Kruskal算法 { cout<<"Kruskal:"<<endl; int i,total,min,minnum,fu,fv; total = n-1; while(total>0) { min = 10000000; for(i=1;i<=m;i++) //找最小值 { if(u[i] == -1||v[i] == -1) continue; if(edge[i]<min) { min = edge[i]; minnum = i; } } fu = find(u[minnum]); fv = find(v[minnum]); if(fu!=fv) //不连通,就连接两个点 { cout<<u[minnum]<<","<<v[minnum]<<":"<<edge[minnum]<<endl; pre[fu] = fv; total--; } edge[minnum] = 100000000; //改变已经找到的最小值 u[minnum] = -1; v[minnum] = -1; } } int main() { cin>>n>>m; int i,a,b,tem; for(i=1;i<=n;i++) pre[i] = i; for(i=1;i<=m;i++) { cin>>a>>b; cin>>tem; u[i] = a; v[i] = b; edge[i] = tem; } kruskal(); return 0; }View Code
运行结果:
Kruskal算法所需的计算时间为O(eloge)
参考:王晓东《算法设计与分析》
https://blog.csdn.net/crystal_viv/article/details/79571545
内容总结
以上是互联网集市为您收集整理的贪心法之prim算法和Kruskal算法全部内容,希望文章能够帮你解决贪心法之prim算法和Kruskal算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。