拓扑排序的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需要注意的问题