拓扑排序

本节讨论一个关于有向图的重要问题。首先我们复习一下有关有向图的一些基本知识。

有向图是一个对所有的边都指定方向的图（如图a).

邻接矩阵和邻接链表是两种表示有向图的主要方式。用这两种方式表示时，无向图和有向图只有两个显著的差异：

1. 有向图的邻接矩阵不一定表现出对称性；
2. 有向图的一条边在图的邻接链表中只有一个相应的节点（不是两个）。

对于有向图的遍历，深度优先查找和广度优先查找是主要的遍历算法，但相应森林的结构可能会更复杂。因此，图a的深度优先查找森林包含了四种类型的边.

1. 树向边(ab, bc, de)
2. 从顶点到祖先的回边(ba)
3. 从顶点到树中非子女子孙的前向边(ac)
4. 交叉变(dc)，所有不属于前三种类型的边都属于交叉边类型

DFS森林的回边意味着该有向图具有一个有向的回路。（如图b）如果一个有向图的DFS森林没有回边，该有向图是一个无环有向图.

对图的边引入方向以后，相比无向图会出现一个新的问题。

本节中我们讨论其中一个问题。作为启发大家的例子，我们考虑五门必修课的一个集合{C1, C2, C3, C4, C5},按照任何次序学习这些课程，需要满足这些先决条件：C1和C2没有任何先决条件，修完C1和C2才能修C3，修完C3才能修C4，而修完C3，C4才能修C5.这个学生每个学期只能修一门课程，这个学生应该按照什么顺序来学习这些课程？

这种状态用一个图来建模，它的顶点代表课程，有向边表示先决条件（图4.6）

就这个图来说，上面这个问题转化为：我们按照这种次序列出它的顶点，使得图中每一条边，边的起始顶点总是排在边的结束顶点之前。这个问题称为拓扑排序.拓扑排序成为可能的必要充分条件是该问题中的图是无环有向图。有两种高效的算法，既可以验证一个有向图是否是一个无环有向图，又可以在是的情况下，输出拓扑排序的一个顶点序列。

第一种算法是深度优先查找的一个简单应用：执行一次DFS遍历，记住顶点变成死端（即退出遍历栈）的顺序。将该次序反过来就得到了拓扑排序的一个解。

这个算法为什么是有效的呢？当一个顶点v退出DFS栈的时候，在比v更早出栈的顶点中，不存在一个顶点u，拥有一条从u到v的边（否则，(u, v)会成为一条回边）。所以，在退栈次序的队列中，任何这样的顶点u都会排在v的后面，并且在逆序队列中会排在v的前面。

图(a)需要进行拓扑排序问题的有向图

图(b)DFS遍历栈，下标数字指出出栈的次序

图(c)为该问题的解

第二种算法基于减（减一）治技术的一个直接实现：不断地做这样一件事，删除余下有向图的一个源，即一个没有输入边的顶点，然后把它和所有从它出发的边都是删除。（如果有多个这样的源，任意选择一个。顶点被删除的次序就是拓扑排序的一个解。图4.8给出了应用该算法对同一个表示五门课程的图的求解过程。

拓扑排序问题的源删除算法，在每次迭代的时候，没有输入边的顶点从有向图中删除。

注意，使用源删除算法获得的解和基于DFS的算法求得的解是不同的。当然，它们两者都是正确的。因此，拓扑排序问题可能会有若干个不同的可选解。

现在请想象一个庞大的项目——比如建筑项目或者研究研究项目——它可能会包含数以千计的相互关联的任务，并且具有已知的先决条件。在这种情况下，我们需要做的第一件事就是确定给定的先决条件的集合是不矛盾的。做到这一点的一个便利方法就是对该项目的图，求一个拓扑排序的解。只要做到了这一点，我们将才能开始安排我们的任务，就是使得整个项目的总完成时间最短。这当然需要另一种算法的支持，比如CPM(Critical Path Method, 关键路径法)和PERT(程序评估和检查技术).