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

1、Kruskal算法求最小生成树（JAVA）代码：packagehomework;importjava.util.Scanner;importjava.util.Arrays;importjava.util.ArrayList;classEdgepublicintstart;/始边publicintend;/终边publicdoublecost;/权重publicclassMinSpanningTree_KruskalprivatestaticintMAX=100;privateArrayListvEdgeedge=newArrayListvEdge();整个图的边privateArrayLis

2、tvEdgetarget=newArrayListvEdge();目标边，最小生成树privateintparent=newintMAX;标志所在的集合privatestaticdoubleINFINITY=99999999.99;/定义无穷大privatedoublemincost=0.0;/最小成本privateintn;结点个数publicMinSpanningTree_Kruskal()publicstaticvoidmain(Stringargs)MinSpanningTree_Kruskalsp=newMinSpanningTree_Kruskal();sp.init();sp.k

3、ruskal();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.nextInt();q=scan.nextInt();w=scan.nextDouble();if(p0|q0|w0)break;Edgee=newEdge();e.s

4、tart=p;e.end=q;e.cost=w;edge.add(e);mincost=0.0;for(inti=1;i=n;+i)parenti=i;/集合合并publicvoidunion(intj,intk)for(inti=1;i=n;+i)if(parenti=j)parenti=k;/prim算法主体publicvoidkruskal()/找剩下的n-2条边inti=0;while(i0)/每次取一最小边，并删除doublemin=INFINITY;inttag=0;Edgetmp=null;for(intj=0;jedge.size();+j)Edgett=edge.get(j)

5、;if(tt.costmin)min=tt.cost;tmp=tt;intjj=parenttmp.start;intkk=parenttmp.end;/去掉环if(jj!=kk)+i;target.add(tmp);mincost+=tmp.cost;union(jj,kk);edge.remove(tmp);if(i!=n-1)System.out.println(没有最小生成树)；System.exit(O);/打印结果publicvoidprint()doublesum=0;System.out.println(”最小生成树：”)；for(inti=0;itarget.size();+i)Edgee=target.get(i);System.out.println(”第+(i+1)+条边:+e.start+e.end+权值：+e.cost);sum=sum+e.cost;System.out.println(”最小生成树的权值：+sum);调试结果：请输入结点个数：请输入各条边及权值（每灰输入一