kruskal算法求最小生成树

《kruskal算法求最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、kruskal算法求最小生成树课题：用kruskal算法求最小生成树。编译工具：VisualStudio2017kruskal算法基本思想：先构造一个只含n个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有n-1条边为止。691044271481184e1e2e3e7e5e6e4问题：按如下连通

2、图用kruskal算法求最小生成树。程序源码：#include#includeusingnamespacestd;constintN=100;intnodeset[N];intn,m;structEdge{//定义结构体.intu;intv;intw;}e[N*N];boolcomp(Edgex,Edgey){//配合sort()方法对权值进行升序。returnx.w

3、]=i;}intMerge(inta,intb)//将e[i].u结点传递给a;e[i].v结点传递给b.{intp=nodeset[a];//p为a结点的集结号，intq=nodeset[b];//q为b结点的集结号.if(p==q)return0;//判断结点间是否回环。若两个结点的集结号相同，则不操作，直接返回。for(inti=1;i<=n;i++)//若两个结点的集结号不相同，检查所有结点，把集合号是q的改为p.{if(nodeset[i]==q)nodeset[i]=p;}return1;}intKruskal(intn){intans

4、=0;for(inti=1;i<=m;i++)if(Merge(e[i].u,e[i].v)){cout<<"A结点："<B结点："<>n>>m;Init(n);cout<<"输入结点数(u),(v)和权值(w)："<>e[i].u>>e

5、[i].v>>e[i].w;sort(e+1,e+m+1,comp);intans=Kruskal(n);cout<<"最小的花费是："<

6、4510e[11]2611e[12]2714(4)调用kruskal(n)方法，(n=7,m=12)。for(inti=1;i<=m;i++)if(Merge(e[i].u,e[i].v))//调用intMerge(inta,intb)方法{cout<<"A结点："<B结点："<

7、p为a结点的集结号，intq=nodeset[b];//q为b结点的集结号.if(p==q)return0;//判断结点间是否回环。若两个结点的集结号相同，则不操作，直接返回。for(inti=1;i<=n;i++)//若两个结点的集结号不相同，检查所有结点，把集合号是q的改为p.{if(nodeset[i]==q)nodeset[i]=p;}return1;}(5)示意图分析abnodeset[a]nodeset[b]pq373737121212353535563636573333673333161313231111341414nodeset[i

8、]ansn12345632611345632+4511343632+4+4411343332+4+4+43回环，直接返回回