waysun一路陽光

          不輕易服輸,不輕言放棄.--心是夢的舞臺,心有多大,舞臺有多大。踏踏實實做事,認認真真做人。

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks
          來源:http://blog.chinaunix.net/u1/50399/showart_407408.html
          /*
           * @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
          posted on 2009-04-15 22:20 weesun一米陽光 閱讀(371) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 阿城市| 固原市| 涿鹿县| 松原市| 拜泉县| 弥渡县| 巩留县| 临漳县| 睢宁县| 云梦县| 太湖县| 绥化市| 郯城县| 南京市| 龙井市| 呼图壁县| 梓潼县| 康平县| 嘉峪关市| 中江县| 安国市| 揭西县| 曲周县| 攀枝花市| 苏尼特左旗| 抚顺市| 仙游县| 美姑县| 合川市| 辽阳县| 白城市| 高邮市| 柳州市| 兴宁市| 新龙县| 陆丰市| 沭阳县| 扶余县| 睢宁县| 怀安县| 武隆县|