最小生成树的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