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源碼 、總結備用
          主站蜘蛛池模板: 高尔夫| 宜宾县| 察隅县| 禄丰县| 巴林右旗| 牟定县| 新龙县| 五家渠市| 沐川县| 吉首市| 南通市| 西乌珠穆沁旗| 那坡县| 阜南县| 抚宁县| 乐业县| 怀仁县| 武宣县| 宁蒗| 万载县| 定结县| 乌审旗| 甘南县| 中方县| 尖扎县| 阿拉尔市| 准格尔旗| 宁安市| 济南市| 富裕县| 沾化县| 鄢陵县| 桂东县| 扶沟县| 汝南县| 通辽市| 临泽县| 全州县| 林口县| 隆子县| 章丘市|