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

1、Kruskal算法求最小生成樹（JAVA）代碼：packagehomework;importjava.util.Scanner;importjava.util.Arrays;importjava.util.ArrayList;classEdgepublicintstart;/始邊publicintend;/終邊publicdoublecost;/權(quán)重publicclassMinSpanningTree_KruskalprivatestaticintMAX=100;privateArrayListvEdgeedge=newArrayListvEdge();整個(gè)圖的邊privateArrayLis

2、tvEdgetarget=newArrayListvEdge();目標(biāo)邊，最小生成樹privateintparent=newintMAX;標(biāo)志所在的集合privatestaticdoubleINFINITY=99999999.99;/定義無(wú)窮大privatedoublemincost=0.0;/最小成本privateintn;結(jié)點(diǎn)個(gè)數(shù)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(請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：)；n=scan.nextInt();System.out.println(”請(qǐng)輸入各條邊及權(quán)值(每次輸入一組數(shù)據(jù)按回車確認(rèn)，+最后輸入-1-1-1結(jié)束輸入過(guò)程);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;/去掉環(huán)if(jj!=kk)+i;target.add(tmp);mincost+=tmp.cost;union(jj,kk);edge.remove(tmp);if(i!=n-1)System.out.println(沒(méi)有最小生成樹)；System.exit(O);/打印結(jié)果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+權(quán)值：+e.cost);sum=sum+e.cost;System.out.println(”最小生成樹的權(quán)值：+sum);調(diào)試結(jié)果：請(qǐng)輸入結(jié)點(diǎn)個(gè)數(shù)：請(qǐng)輸入各條邊及權(quán)值（每灰輸入一