waysun一路陽光

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

            BlogJava :: 首頁 :: 新隨筆 :: 聯系 ::  :: 管理 ::
            167 隨筆 :: 1 文章 :: 64 評論 :: 0 Trackbacks
          來源:http://blog.chinaunix.net/u1/50399/showart_408098.html
          /*
           * @title:拓撲排序
           * @input: 一個有向無環圖,表述為一個鄰接矩陣graph[n][],其中graph[i][0]為頂點i的入度,其余為其后繼結點
           * @output: 一個拓撲序列list
           */

          import java.util.*;
          public class TopologicalSortTest
          {  
             public static void main(String[] args)
             {
                 int[][] graph={{0,1,2,3,},{2,},{1,1,4,},{2,4,},{3,},{0,3,4,},};
                 int[] list=new int[graph.length];;
                 TopologicalSort topologicalSort=new TopologicalSort();
                 topologicalSort.input(graph);
                 list=topologicalSort.getList();
                 for(int l : list){
                     System.out.print(l+" ");
                 }
             }
          }
          class TopologicalSort
          {
           int[][] graph;
           int[] list;
           
              void input(int[][] graph)
              {
               this.graph=graph;
               list=new int[graph.length];
               calculate();
              }
              
              void calculate()
              {
                  Stack stack=new Stack();
                  for(int i=0; i<graph.length; i++){
                   if(graph[i][0]==0){
                    stack.push(i);
                   }
                  }
                  
                  int i=0;
                  while(stack.empty()!=true){
                   list[i]=(Integer)stack.pop();
                   for(int j=1; j<graph[list[i]].length; j++){
                    int k=graph[list[i]][j];
                    if((--graph[k][0])==0){
                     stack.push(k);
                    }
                   }
                   i++;
                  }
                  
                  if(i<graph.length){
                   System.out.println("存在環,不可排序!");
                   System.exit(0);
                  }
              }
              int[] getList()
              {
               return list;
              }
          }
           
          運行結果:
          5 0 3 2 4 1
          posted on 2009-04-15 22:22 weesun一米陽光 閱讀(418) 評論(0)  編輯  收藏 所屬分類: JAVA源碼總結備用
          主站蜘蛛池模板: 鄄城县| 漳州市| 噶尔县| 房山区| 扶沟县| 吴江市| 道孚县| 叙永县| 武功县| 石渠县| 登封市| 蒙城县| 玉环县| 松江区| 麻阳| 察雅县| 高安市| 唐海县| 南澳县| 霍林郭勒市| 内丘县| 宝鸡市| 务川| 文登市| 精河县| 浮山县| 东山县| 渝中区| 策勒县| 抚松县| 盘山县| 永康市| 蛟河市| 海林市| 安国市| 延川县| 宝丰县| 衡水市| 莎车县| 沈丘县| 明水县|