22.4 拓扑排序

拓扑排序

本节阐述如何使用深度优先搜索来对有向无环图进行拓扑排序。对于一个有向无环图G=(V,E)来说，其拓扑排序是G中所有结点的一种线性次序，该次序满足如下条件:如果图G包含边(u，v)，则结点u在拓扑排序中处于结点v的前面(如果图G包含环路，则不可能排出一个线性次序)。可以将图的拓扑排序看做是将图的所有结点在一条水平线上排开，图的所有有向边都从左指向右。因此，拓扑排序与本书第二部分所讨论的通常意义上的“排序”是不同的。

下面的简单算法可以对一个有向无环图进行拓扑排序:

TOPOLOGICAL-SORT(G)

call DFS(G) to compute finishing times v.f for reach vertex v//调用DFS（G）计算到达顶点v的完成时间v.f
as each vertex is finished,insert it onto the front of a linked list//完成每个顶点后，将其插入到链接列表的前面
return the linked list of vertices//返回顶点的链接列表

引理 22.11 有向无环图的特征

一个有向图G=(V，E)是无环的当且仅当对其进行的深度优先搜索不产生后向边。

证明

定理 22.12

拓扑排序算法TOPOLOGICAL-SORT生成的是有向无环图的拓扑排序。

证明

练习

22.4-4

证明或反证：如果一个有向图G包含圈，那么拓扑排序（G）产生一个顶点排序，该排序将最小化与生成的排序不一致的“坏”边的数量。

Solution

事实并非如此。考虑由顶点A、B、C和D组成的图G。设边为（a，b）、（b，c）、（a，d）、（d，c）和（c，a）。假设我们从顶点c开始拓扑排序的DFS。假设在a的邻接列表中，b出现在d之前，完成时间从最晚到最早的顺序是c、a、d、b。

这种情况下的“坏”边是（b，c）和（d，c）。然而，如果我们按a，b，d，c顺序排列，那么唯一的坏边就是（c，a）。因此，拓扑排序并不总是最小化“坏”边的数量。