Kruskal贪心算法实现.doc

《Kruskal贪心算法实现.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、packagecom.jungoo.chapter8;importjava.util.ArrayList;importjava.util.List;/***输入一个带权的连通无向图生成该图的最小生成树该类实现Kruskal算法该算法以边为主适用于边多点少的图形中**@authoradministrator*/publicclassKruskal{/***代表字符的数字A-0,B-1,C-2,D-3，E-4*///当两个顶点没有连线的时候将其权值设为MOUSTMAXprivatestaticfinalintMOUSTMAX=1000;//保存点集

2、的第一个集合privatestaticListSTART=newArrayList();//保存点集的第二个集合privatestaticListEND=newArrayList();/***@paramarray*带权值的二维数组*/publicstaticvoidsort(int[][]array){intmin=array[0][0];//找到当前二维数组中最小的值for(inti=0;i

3、;j++){if(array[i][j]<=min){min=array[i][j];}}}//定义两个变量存储相应坐标，二维数组中有array[0][0]所以如下定义intvarx=Integer.MAX_VALUE;intvary=Integer.MAX_VALUE;//将最小处的值改变for(inti=0;i

4、将数字转化成字符Stringcharx=Kruskal.tochar(varx);Stringchary=Kruskal.tochar(vary);//判断是否有环路Listlaststring=Kruskal.dest(charx,chary);for(Stringi:laststring){System.out.print(i+"");}}/***判断是否构成回路*@paramcharx*X坐标*@paramchary*Y坐标*@returnList*String*/publicstaticListdest(

5、Stringcharx,Stringchary){Listlast=newArrayList();//初始点集为空时if(END.size()==0){last.add(charx+chary);END.add(charx);END.add(chary);}else{//边的坐标并不全在两个点集中的任何一个点集中,如果在任何一个点集就会构成回路if(!(END.contains(charx)&&END.contains(chary)

6、

7、START.contains(charx)&&START.contains(c

8、hary))){//如果某点在一个点集中，另一个点在另一个点集中if(END.contains(charx)&&START.contains(chary)){last.add(charx+chary);//构成新的点集for(Stringchar1:START){if(!END.contains(char1)){END.add(char1);}}START.clear();}elseif(START.contains(charx)&&END.contains(chary)){last.add(charx+chary);for(Stringcha

9、r1:START){if(!END.contains(char1)){END.add(char1);}}}//如果两点都不在某点集中,那么添加另外一个集合保存新的点集,把这个新的节点保存才START链表中elseif(!END.contains(charx)&&!END.contains(chary)){last.add(charx+chary);if(!START.contains(charx)&&!START.contains(chary)){START.add(charx);START.add(chary);}if(START.conta

10、ins(charx)&&!START.contains(chary)){START.add(chary);}if(!START.contains(ch