拓扑排序的实现

什么是拓扑排序呢？首先我们来了解一下另一个词：什么是“拓扑序”？

拓扑序：在图中从顶点A到顶点B有一条有向路径，则顶点A一定排在顶点B之前。满足这样的条件的顶点序列称为一个拓扑序。

而获得一个拓扑序列的过程就称为拓扑排序。我们来看个例子：

通常大学的课程安排不是盲目的，例如，如果你想学习离散数学，前提你必须要预修高等数学这门课。如果你想学习数据结构这门课，那么你要先学了程序设计这门课，等等等等。所以一般大学都会根据课程之间的联系来安排学生学习课程的先后次序。上面这张表就显示出了一些课程之间的联系，如何用数据结构来表示这张图中的课程之间的关系？

这里就要用到有向图。图中的每一个顶点对应每一门课，边表示的是两个顶点之间（两门课之间）的关系，如果两门课之间是有预修关系的，即如果前一门课是后一门课的预修课程，那么表示这两门课的两个顶点间就有一条有向边。

搞清楚图中的两个要素，即顶点和边的表示之后，那么就要开始构造这张表示上面课程关系的图了。首先我们找到没有预修课程的课做为起点。例如这里是A1，A2和A6。

起点顶点找完出来后，开始看它们和其他课程之间的关系了，首先按顺序，我们看A3离散数学课程，它的预修课程是A2，所以把A3顶点放进如中，然后把A2顶点指向A3顶点。

接着再看A4数据结构课程，它的预修课程是A1和A3，所以把A4顶点放进图中，然后更新图，即把A1顶点和A3顶点指向A4顶点。

A4课程排完了接着到A5算法设计，算法设计的预修课程是程序设计和数据结构，所以把A5放进图里后，让A1和A4结点都指向它：

A6没有预修课程，是个起点顶点，所以跳过，到A7线性代数课程，它的预修课程是A2高等数学，同样把A7放到图里后，再让A2指向A7即可

最后到A8嵌入式系统，预修课程有A3和A6，就把A8放进图里，然后把A3和A6两个个顶点都指向A8即可。

这样一张课程之间的关系图就完成了。这样的图符合我们上面说的拓扑序，所以这样的图我们称为AOV（Activity On Vertex）网络，意思是在这张有向图中，里面的活动是表示在顶点上的（或者说用一个顶点来表示一项活动或工作）。而顶点对（即两个顶点之间）的边表示的是两个顶点活动的顺序。再重温一下上面说的拓扑序的概念：拓扑序：在图中从顶点A到顶点B有一条有向路径，则顶点A一定排在顶点B之前。简单来说，就是A顶点的输出一定是发生在B顶点之前。

这里有一个概念：一个AOV网络，如果有合理的拓扑序，那么该图一定是有向无环图。有向无环图也称作流程图，图中的每一个顶点称作一个工序，每条边反应了边上两个工序的前后次序。为什么一定是无环图呢？如果图是有环的话，那么会出现这样的情况，一个顶点A的有向边指向了自己，那么对于顶点A来说，它既是自己的前驱顶点，也是自己的后驱顶点，这样的关系就出问题了。或者两个顶点B和C成环的话，那么既可以认为B是C的前驱顶点，也可以认为C是B的前驱顶点，这样同样是不行，它们的前后顺序是不确定的，所以如果一个有向图中存在环（即存在回路），那么这个有向图一定不能得到一个合理的拓扑序。

 

得到一个有向无环图来表示上面课程之间的关系之后，我们只是得到课程之间的关系，根据这个AOV网络，我们要怎么进行拓扑排序？一个一个来，首先我们同样从没有预修课程的课开始，即顶点A1，A2和A6。首先输出A1，就是把A1从AOV网络中删除。

注意这里的删除操作，不仅是从图中删除顶点A1，还要把A1的出度边都删除。

然后到A2顶点，把A2顶点输出，同时删除A2的所有出度边。

然后到A6：

同样的方法我们接着对A3,A4和A7三个顶点操作：

最后把剩下的两个顶点A5和A8也排上去，就完成了：

最后到了代码实现，根据我们上面的做法，每次我们都是把一个入度为0的顶点先输出，然后再删除与该顶点相连的边，所以这里我们的图的结构用邻接表表示更好。

函数里我们传进去我们的图，AOV网络MyGraph，和一个存放顶点的数组TopOrder，这个数组是用来存放我们输出的顶点的，也就是我们拓扑排序后得到的序列。

然后从第215行开始，我们要一个Indefree数组来存放顶点的入度情况，还要一个邻接表表示的图W，cnt是计数器，用来记录图中经过操作的顶点的个数，因为如果在程序最后经过操作的顶点数不等于AOV网络中的顶点数，那么说明这个AOV网络是有回路的。最后我们还需要一个队列PtrQ，这个队列是用来存放入度为0的顶点的，当我们一开始，和操作过程中，发现有入度为0的顶点时，就把它入队列，接着每次操作时就从队列里出列一个入度为0的顶点。这样做可以降低程序的时间复杂度，因为我们不用每一次都去扫描一遍整个AOV网络找出一个入度为0的顶点，我们在一开始和操作过程中，凡是找到一个入度为0的顶点，都把它入列，这样简化了很多。

把要用到的工具都定义好后，接着开始初始化，第220行首先初始化入度数组为0。接着遍历AOV网络，把它们的入度情况更新到Indegree数组里，如果某个顶点的头指针时存在的，即这个顶点有前驱顶点的，就把响应的该顶点的下标的Indegree数组++。接着第233行再遍历一次图把一开始入度为0的顶点入队列。这样就把初始化工作做好了。

最后进行拓扑排序，第242行，while循环当队列PtrQ->front！=NULL，队列不为空时（即队列中有入度为0的顶点），就从队列中出列一个入度为0的顶点，把该顶点记录在TopOrder数组中，然后遍历这个顶点V的每一个邻接点，如果把顶点V删除后，某个邻接点的入度变为0的话，就把该顶点入队列，这样一次重复下去，一直做到队列为空，即所有入度为0的顶点都出列完后，就结束while循环。最后的最后，第255行，判断计数器cnt和图中的所有顶点数是否相等，如果不相等，说明该图里存在回路，就返回false，否则，如果相等，就返回true。