Kruskal算法求最小生成树(java)

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

1、Kruskal算法求最小生成树（JAVA）代码：packagehomework;importjava.util.Scanner;importjava.util.Arrays;importjava.util.ArrayList;classEdge{publicintstart;//始边publicintend;//终边publicdoublecost;//权重}publicclassMinSpanningTree_Kruskal{privatestaticintMAX=100;privateArrayListedge=newArrayList

2、();//整个图的边privateArrayListtarget=newArrayList();//目标边，最小生成树privateint[]parent=newint[MAX];//标志所在的集合privatestaticdoubleINFINITY=99999999.99;//定义无穷大privatedoublemincost=0.0;//最小成本privateintn;//结点个数publicMinSpanningTree_Kruskal(){}publicstaticvoidmain(Stringargs[]){MinSpannin

3、gTree_Kruskalsp=newMinSpanningTree_Kruskal();sp.init();sp.kruskal();sp.print();}//初始化publicvoidinit(){Scannerscan=newScanner(System.in);intp,q;doublew;System.out.println("请输入结点个数：");n=scan.nextInt();System.out.println("请输入各条边及权值（每次输入一组数据按回车确认，"+"最后输入-1-1-1结束输入过程）");while(true){p=scan.

4、nextInt();q=scan.nextInt();w=scan.nextDouble();if(p<0

5、

6、q<0

7、

8、w<0){break;}Edgee=newEdge();e.start=p;e.end=q;e.cost=w;edge.add(e);}mincost=0.0;for(inti=1;i<=n;++i){parent[i]=i;}}//集合合并publicvoidunion(intj,intk){for(inti=1;i<=n;++i){if(parent[i]==j){parent[i]=k;}}}//prim算法主体publicvoidkrus

9、kal(){//找剩下的n-2条边inti=0;while(i0){//每次取一最小边，并删除doublemin=INFINITY;inttag=0;Edgetmp=null;for(intj=0;j

10、p.cost;union(jj,kk);}edge.remove(tmp);}if(i!=n-1){System.out.println("没有最小生成树");System.exit(0);}}//打印结果publicvoidprint(){doublesum=0;System.out.println("最小生成树：");for(inti=0;i

11、m=sum+e.cost;}System.out.println("最小生成树的权值："+sum);}}调试结果：