Chinaunix首页 | 论坛 | 博客
  • 博客访问: 127301
  • 博文数量: 49
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: -15
  • 用 户 组: 普通用户
  • 注册时间: 2016-07-03 22:22
个人简介

小楼一夜听春雨

文章分类
文章存档

2017年(1)

2016年(2)

2015年(5)

2014年(21)

2013年(5)

2012年(7)

2010年(6)

2009年(2)

我的朋友

分类: Java

2010-10-31 23:10:19

/*
 * @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
阅读(1938) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~