对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若存在由u到v的路径，则在拓扑排序序列中一定是u出现在v的前边。

在一个有向图中找到一个拓扑排序序列的过程如下：

1）从有向图中选择一个没有前驱（入度为0）的顶点输出；

2）删除1）中的顶点，并且删除从该顶点发出的全部边；

3）重复上述两步，直到剩余的图中不存在没有前驱的顶点为止。

以邻接表为存储结构，怎样实现拓扑排序的算法呢？因为上述步骤中提到要选取入度为0的结点并将其输出，要对邻接表表头结构定义进行修改，可加上一个统计结点入度的计数器，修改如下：

假设图的邻接表已经生成，并且各个顶点的入度都已经记录在count中，在本算法中要设置一个栈，用来记录当前图中入度为0的顶点，还要设置一个计数器n，用来记录已经输出的顶点个数。

算法开始时置n为0，扫描所有顶点，将入度为0的顶点入栈。然后在栈不空的时候循环执行：出栈，将出栈顶点输出，执行++n，并且将由此顶点引出的边所指向的顶点的入度都减1，并且将入度变为0的顶点入栈；出栈，…，栈空时循环退出，排序结束。循环退出后判断n是否等于图中的顶点个数。如果相等则返回1，拓扑排序成功；否则返回0，拓扑排序失败。

由此可以写出以下算法代码：

注意：拓扑排序序列可能不唯一。从算法过程中可以看出，在选择入度为0的顶点输出的时候，对顶点没有其他要求，只需入度为0即可。当前步骤中有多个入度为0的顶点时，可以任选一个输出，这就造成了拓扑排序序列不唯一。

若AOV网中考查各顶点的出度并以下列步骤进行排序，则将这种排序称为逆拓扑排序，输出的结果称为逆拓扑有序序列。

1）在网中选择一个没有后继的顶点（出度为0）输出；

2）在网中删除该顶点，并删除所有到达该顶点的边；

3）重复上述两步，直到AOV网中已无出度为0的顶点为止。

注意：当有向图中无环的时候，还可以采用深度优先搜索遍历的方法进行拓扑排序。由于图中无环，当由图中某顶点出发进行深度优先搜索遍历时，最先退出算法的顶点即为出度为0的顶点，它是拓扑有序序列中的最后一个顶点。因此，按照DFS算法的先后次序记录下的顶点序列即为逆向的拓扑有序序列。(www.daowen.com)

关于这个注意的内容，有不少同学通过微信反映理解上有困难，下面就其中两句话详细解释一下。

1.“最先退出算法的顶点即为出度为0的顶点。”

2.“按照DFS算法的先后次序记录下的顶点序列。”

第1句话中退出算法是指所遍历的顶点退出当前系统栈。

第2句话中按照DFS算法先后次序并不是指最终遍历结果序列，而是顶点退出系统栈的顺序。

例如，图{A-＞B，A-＞C，B-＞D，C-＞D}的一种深度优先遍历进出栈过程为：

A入栈（栈中元素为A）；

B入栈（栈中元素为AB）；

D入栈（栈中元素为ABD）；

D出栈（栈中元素为AB，D为第一个出栈元素）；

B出栈（栈中元素为A，B为第二个出栈元素）；

C入栈（栈中元素为AC）；

C出栈（栈中元素为A，C为第三个出栈元素）；

A出栈（栈空，A为第四个出栈元素）。因此各个元素出栈先后序列为DBCA，为拓扑序列ACBD的逆拓扑序列。