拓扑排序的java实现

文章作者 100test 发表时间 2011:03:18 19:40:08
来源 100Test.Com百考试题网

　　/*

　　* @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

　　编辑特别推荐:

　　#0000ff>关键路径的java实现

　　#0000ff>应对java中文乱码的妙招

　　#0000ff>Java利用poi读写Excel需要注意的问题