Prim算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Prim算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2690字,纯文字阅读大概需要4分钟。
内容图文
![Prim算法](/upload/InfoBanner/zyjiaocheng/846/1ac05166972549418cb460e94fafc519.jpg)
一个连通图的生成树是该连通图的一个极小连通子图,它是含有图的全部顶点,但只有构成一棵树的(n-1)条边,而最小生成树则是在生成树的基础上,要求树的(n-1)条边的权值之和是最小的。
由此可以总结构造最小生成树的要求有:
(1)必须只使用该图中的边来构造最小生成树
(2)必须使用且仅使用(n-1)条边来连接图中的n个顶点
(3)不能使用产生回路的边
(4)要求树的(n-1)条边的权值之和是最小的
大致思想是:设图G顶点集合为U,首先任意选择图G中的一点作为起始点a,将该点加入集合V,再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小,此时将b点也加入集合V;以此类推,现在的集合V={a,b},再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小,此时将c点加入集合V,直至所有顶点全部被加入V,此时就构建出了一颗MST。
因为有N个顶点,所以该MST就有N-1条边,每一次向集合V中加入一个点,就意味着找到一条MST的边。
#include <iostream> #include <vector> #define INF 0x3f3f using namespace std; class Graph { public: Graph(); ~Graph(); void prim(int start); private: int num;//点的个数 int edges;//边的个数 int **array;//邻接矩阵 }; Graph::Graph() { cout<<" 请输入图的顶点的个数:"<<endl; cin>>num; cout<<" 请输入图的边数:"<<endl; cin>>edges; cout<<" 请输入每条边的两个顶点的编号:"<<endl; int **e_info=new int*[edges];//临时的数组构造函数结束可释放 for(int i=1;i<=edges;++i) { e_info[i]=new int[2]; cin>>e_info[i][0]>>e_info[i][1]; } //为邻接矩阵开辟空间并初始化 array=new int*[num];//为邻接矩阵开辟空间,一维数组 for(int i=1;i<=num;++i) { array[i]=new int[num];//二维数组 for(int j=1;j<=num;++j) array[i][j]=INF; } //根据无向图的边的起始坐标和结束坐标构建邻接矩阵,数组中下标均是从0开始,所以需要减1 for(int i=1;i<=edges;++i) { cin>>array[e_info[i][0]][e_info[i][1]]; array[e_info[i][1]][e_info[i][0]]=array[e_info[i][0]][e_info[i][1]]; } //释放e_info for(int i=1;i<=edges;++i) delete []e_info[i]; } Graph::~Graph() { for(int i=1;i<=num;++i) delete []array[i]; } void Graph::prim(int start) { int lowcost[num],close[num]; for(int i=1;i<=num;++i) { lowcost[i]=array[start][i];//lowcost为start-->i的权值 close[i]=start;//现在最小生成树集合中只有start,把start加入集合(V集合) } lowcost[start]=0;//标记为0,用过,不再用 for(int i=2;i<=num;++i)//num个结点则就有num-1条边 { int min=INF,step=0; for(int j=1;j<=num;++j)//找出到j边中权值最小的一条边,第一次执行找的是start-->j if(lowcost[j]!=0&&lowcost[j]<min) { step=j; min=lowcost[j]; } cout<<close[step]<<" -->"<<step<<" 权值:"<<min<<endl; lowcost[step]=0; for(int j=1;j<=num;++j)//如果由于新加入的结点导致其他节点到生成树的值变小,则更新值,并且把该结点加入到生成树的集合中 if(lowcost[j]!=0&&array[step][j]<lowcost[j]) { lowcost[j]=array[step][j]; close[j]=step; } } } int main() { Graph g; cout<<" 请输入prim的开始位置:"<<endl; int start; cin>>start; g.prim(start); return 0; }
详细图解请参考:https://blog.csdn.net/yeruby/article/details/38615045
内容总结
以上是互联网集市为您收集整理的Prim算法全部内容,希望文章能够帮你解决Prim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。