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