拓扑排序的java实现

《拓扑排序的java实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、拓扑排序的java实现/*　　*@title：拓扑排序　　*@input:一个有向无环图，表述为一个邻接矩阵graph[n][]，其中graph[i][0]为顶点i的入度，其余为其后继结点　　*@output:一个拓扑序列list　　*/　　importjava.util.*;　　publicclassTopologicalSortTest　　{　　publicstaticvoidmain(String[]args)　　{　　int[][]graph={{0,1,2,3,},{2,},{1,1,4,},{2,4,},{3,},{0,3,4,},};　　

2、int[]list=newint[graph.length];;　　TopologicalSorttopologicalSort=newTopologicalSort();　　topologicalSort.input(graph);　　list=topologicalSort.getList();　　for(intl:list){　　System.out.print(l+"");　　}　　}　　}　　classTopologicalSort　　{　　int[][]graph;　　int[]list;　　voidinput(int[][]graph)　

3、　{　　this.graph=graph;　　list=newint[graph.length];　　calculate();　　}　　voidcalculate()　　{　　Stackstack=newStack();　　for(inti=0;i

　　if(graph[i][0]==0){　　stack.push(i);　　}　　}　　inti=0;　　while(stack.empty()!=true){　　list[i]=(Integer)stack.pop();　　for(intj=1;j<>　　intk=graph[list[i]][j]

4、;　　if((--graph[k][0])==0){　　stack.push(k);　　}　　}　　i++;　　}　　if(i　　System.out.println("存在环，不可排序！");　　System.exit(0);　　}　　}　　int[]getList()　　{　　returnlist;　　}　　}　　运行结果：　　503241