最小生成树的Java实现

文章作者 100test 发表时间 2011:03:18 19:40:09
来源 100Test.Com百考试题网

　　/*

　　* @input: 一个有向无环带权图，表述为一个二维数组graph[n][n]

　　* @output: 最小生成树tree[n-1][3],tree[i][0]及tree[i][1]为边之顶点，tree[i][2]为权

　　*/

　　public class MiniSpanTreeTest

　　{

　　static int[][] graph={

　　{1000,6,1,5,1000,1000},

　　{6,1000,5,1000,3,1000},

　　{1,5,1000,5,6,4},

　　{5,1000,5,1000,1000,2},

　　{1000,3,6,1000,1000,6},

　　{1000,1000,4,2,6,1000},

　　}.

　　static int v=0.

　　static int[][] tree.

　　public static void main(String[] args)

　　{

　　MiniSpanTree miniSpanTree=new MiniSpanTree().

　　miniSpanTree.input(graph, v).

　　tree=miniSpanTree.getTree().

　　for(int i=0. i

　　System.out.println("边：" tree[i][0] "-" tree[i][1] " 权：" tree[i][2]).

　　}

　　}

　　}

　　class MiniSpanTree

　　{

　　private int[][] graph.

　　private int v.

　　private int[][] tree.

　　private boolean[] s.

　　void input(int[][] graph, int v)

　　{

　　this.graph=graph.

　　this.v=v.

　　tree=new int[graph.length-1][].

　　s=new boolean[graph.length].

　　for(boolean i : s) i=false.

　　s[v]=true.

　　calculate().

　　}

　　void calculate()

　　{

　　for(int i=0. i

　　int[][] edge ={{0,0,1000,},}.

　　for(int j=0. j

　　for(int k=0. s[j]==true