kruskal算法求最小生成树.doc

kruskal算法求最小生成树课题:用kruskal算法求最小生成树。编译工具:VisualStudio2017kruskal算法基本思想:先构造一个只含n个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上,则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,也即子图中含有n-1条边为止。691044271481184e1e2e3e7e5e6e4问题:按如下连通图用kruskal算法求最小生成树。程序源码:#include<iostream>#include<algorithm>usingnamespacestd;constintN=100;intnodeset[N];intn,m;structEdge{//定义结构体. intu; intv; intw;}e[N*N];p(Edgex,Edgey){//配合sort()方法对权值进行升序。 <;}voidInit(intn)//对集合号nodeset数组进行初始化.{ for(inti=1;i<=n;i++) nodeset[i]=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=0; for(inti=1;i<=m;i++) if(Merge(e[i].u,e[i].v)) {cout<<"A结点:"<<e[i].u<<"一>B结点:"<<e[i].v<<endl;//输出满足条件的各结点 ans+=e[i].w; n--; if(n==1) returnans; } return0;}intmain(){ cout<<"输入总结点数(n)和总边数(m):"<<endl; cin>>n>>m; Init(n); cout<<"输入结点数(u),(v)和权值(w):"<<endl; for(inti=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w; sort(e+1,e+m+p); intans=Kruskal(n); cout<<"最小的花费是:"<<ans<<endl; return0;}源码流程解析:(1)在main()中,输入结点数n与边m,n=7,m=12。(2)在Init(n)中,对nodeset[i]进行初始化。下标[i]1234567集合号1234567(3)使用sort()方法按权值进行升序排序。e[i]uvwe[1]372e[2]124e[3]354e[4]564e[5]576e[6]677e[7]168e[8]238e[9]