数据结构与算法_拓扑排序

    拓扑排序中的图一定是有方向的。因为有方向能表示两个顶点之间的优先关系，谁在谁的前面。不能形成环，因为一旦形成环了，几个顶点的优先关系就不能排序了。

     一个无环的有向图称为有向无环图（Directed Acycline Graph,DAG）

    有向无环图是描述一个工程，计划，生产，系统等流程的有效工具。一个大工程可分为若干个子工程（活动），活动之间通常有一定的约束，例如先做什么活动，什么活动完成后才可以开始下一个活动。

    用顶点表示活动，用弧表示活动之间的优先关系的有向图，称为顶点表示活动的网（Activity On Vertex Nextwork）,简称AOV网。

    在AOV网中，若从顶点i 到顶点j 之间存在一条有向路径，称顶底 i 是顶点 j 的前驱，或者称顶点 j 是顶点 i 的后继。若<i,j>是图中的弧，则称顶点 i 是顶点 j 的直接前驱，顶点 j 是顶点 i 的直接后驱。

    AOV网中是不允许有环的，否则会出现自己是自己的前驱，陷入死循环，怎么判断AOV网中是否有环呢？ 一个检测的办法是对有向图的顶点进行拓扑排序。如果AOV网中所有的顶点都在拓扑序列中，则AOV网中必定无环。

    拓扑排序是指将AOV网中的顶点排成一个线性序列，改序列必须满足：若从顶点 i 到顶点 j 有一条路径，则该序列中顶点 i 一定在顶点 j 之前。

    如何进行拓扑排序呢？

    拓扑排序的思想：

1）选择一个无前驱的顶点并输出；（程序中就是找入度为零的点）

2）从图中删除该顶点和该顶点的所发出边；

3）重复 1）和 2），直到不存在无前驱的顶点；

4）如果输出的顶点数小于 AOV网中的顶点数，则说明网中有环，否则输出的序列即为拓扑序列。

拓扑排序并不是唯一的。

例如：

在上述的描述过程中，有删除顶点和边的操作，实际上，在程序实现上，完全没必要真的删除顶点和边。可以将没有前驱的顶点（入度为0）暂存到栈中，输出时出栈即表示删除。边的删除只需要将其邻接点的入度减1即可。例如图中，删除C0的所有出发边，相当于将C3,C2,C1顶点入度减1。如下图所示。

   算法步骤：

1） 求出各顶点的入度，存入数组indegeree[]中，并将入度为0的顶点入栈S。

2）如果栈不为空，则重复执行以下操作：

•     栈顶元素 i 出栈，并保存到拓扑序列数组top[]中；
  

•     顶点 i 的所有邻接点入度减1，如果减1后入度为0，立即入栈S。

3）如果输出的顶点数小于AOV网中的顶点数，则说明网中有环，否则输出拓扑序列。

首先第一步：图的存储：邻接矩阵，邻接表，链式前向星