/*
* @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 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 int k=graph[list[i]][j]; if((--graph[k][0])==0){ stack.push(k); } } i++; } if(i System.out.println("存在环，不可排序！"); System.exit(0); } } int[] getList() { return list; } } 运行结果： 5 0 3 2 4 1
