当前所在位置：珠峰网资料 >> 计算机 >> 计算机等级考试 >> 正文
最新资料
最新课程
最新资讯
最新机构
资讯导航
最小生成树的Java实现
发布时间：2010/11/3 14:44:15 来源：城市学习网 编辑：ziteng

　　/*

　　* @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<graph.length-1; 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<graph.length-1; i++){

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

　　for(int j=0; j<graph.length; j++){

　　for(int k=0; s[j]==true && k<graph.length; k++){

　　if(s[k]==false && graph[j][k]<edge[0][2]){

　　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()

　　{

　　return tree;

　　}

　　}

　　结果如下：

　　边：0-2  权：1

　　边：2-5  权：4

　　边：5-3  权：2

　　边：2-1  权：5

　　边：1-4  权：3

最新课程

计算机
广告合作：400-664-0084 全国热线：400-664-0084
Copyright 2010 - 2017 www.my8848.com 珠峰网 粤ICP备15066211号
珠峰网 版权所有 All Rights Reserved