算法复杂度O(n+e) 邻接表实现

                  假设有向图有n个顶点,e条边,首先搜索入度为0的顶点,把它所有的直接后继入度数减一,然后将该顶点输出.重复上述过程直到找不到入度为0的顶点就结束.如果所有顶点都已经输出,说明图中不存在有向环,且输出的序列即为拓扑有序序列.实现过程可以用一个栈来保持当前搜索到入度为0的顶点.所以拓扑排序也可以用来判断图是否为有向环图..

              伪代码如下:

int TopoSort ()

{

       统计所有顶点的入度数并保存;

       找到入度数为0的顶点并入栈;               //为什么要用栈,队列可不可?

       循环0…..n次 (因为要输出n个顶点)

	{

	如果栈空{ return 0; } //说明不存在入度数为0的顶点,但是循环还没结束

                                                    //说明图为有向环图

	取栈顶元素并出栈.输出元素;

	找到该元素的直接后继,入度数减一,同时判断入度数是否为0,为0入栈;

	}

	return 1;

}

参考文献:  <<国际大学生程序设计竞赛例题解>>