最小生成树的Java实现.doc

《最小生成树的Java实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、最小生成树的Java实现/*　　*@input:一个有向无环带权图，表述为一个二维数组graph[n][n]　　*@output:最小生成树tree[n-1][3],tree[i][0]及tree[i][1]为边之顶点，tree[i][2]为权　　*/　　publicclassMiniSpanTreeTest　　{　　staticint[][]graph={　　{1000,6,1,5,1000,1000},　　{6,1000,5,1000,3,1000},　　{1,5,1000,5,6,4},　　{5,100

2、0,5,1000,1000,2},　　{1000,3,6,1000,1000,6},　　{1000,1000,4,2,6,1000},　　};　　staticintv=0;　　staticint[][]tree;　　publicstaticvoidmain(String[]args)　　{　　MiniSpanTreeminiSpanTree=newMiniSpanTree();　　miniSpanTree.input(graph,v);　　tree=miniSpanTree.getTree();　　for(i

3、nti=0;i

　　System.out.println("边："+tree[i][0]+"-"+tree[i][1]+"权："+tree[i][2]);　　}　　}　　}　　classMiniSpanTree　　{　　privateint[][]graph;　　privateintv;　　privateint[][]tree;　　privateboolean[]s;　　voidinput(int[][]graph,intv)　　{　　this.graph=graph;　　this.v=v;　　tree=

4、newint[graph.length-1][];　　s=newboolean[graph.length];　　for(booleani:s)i=false;　　s[v]=true;　　calculate();　　}　　voidcalculate()　　{　　for(inti=0;i

　　int[][]edge={{0,0,1000,},};　　for(intj=0;j<>　　for(intk=0;s[j]==true&&k<>　　if(s[k]==false&&graph[j][k]

5、]){

　　edge[0][0]=j;　　edge[0][1]=k;　　edge[0][2]=graph[j][k];　　}　　}　　}　　tree[i]=edge[0];　　s[tree[i][1]]=true;　　}　　}　　int[][]getTree()　　{　　returntree;　　}　　}　　结果如下：　　边：0-2 权：1　　边：2-5 权：4　　边：5-3 权：2　　边：2-1 权：5　　边：1-4 权：3