topologicalsorttest.java

实现拓扑排序：一个有向无环图

/*
 * @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;
    }
}