有向无环图中的拓扑排序

Topological Sorting

ZingLix June 14, 2018

一、什么是拓扑排序

在一个较为复杂的任务中,我们往往选择将其分解为数个较为简单的分任务,然后依次完成。这些分任务之间,有些具有依赖关系,必须先完成某一个才可以完成接下去的任务。类似于在学校中,为了获得学位,必须将所有课程修完。而在学习数据结构前,必须先学完某一门编程语言。或是如下,算法导论中的一个例子。

这是 Bumstead 教授每天穿衣服的次序图,必须先穿好某些衣服才能穿其他的。而教授必定是一件一件衣服穿的,那么就可以将其变为一副线性的次序图。

如上,将一副有向无环图变成线性序列的过程,称之为拓扑排序(Topological Sorting)。对于线性序列,严格的要求为:

  • 每个顶点出现且只出现一次
  • 如果存在一条边从 A 指向 B ,那么序列中 A 出现在 B 之前。

之所以要求是有向无环图,是因为只有有向才能在两个结点间决定先后次序。而若是有环,那么根据第二个要求,若AB间成环,则存在从 A 到 B 和从 B 到 A 两条边,那么A 要出现在 B 之前,B 也要出现在A之前,在线性序列中不可能实现。

二、实现

拓扑排序利用两种图遍历方法都可以完成。

DFS 实现

试想一下,当每次 DFS 返回的时候,对于该节点的后继必然已全部都访问完毕,那么如果在每次返回的时候输出当前结点,那么我们就可以得到一个逆拓扑序列,或者说输出的时候输出到一个列表的前端那么就是我们想要的结果。

BFS 实现

这一方法又称为 Kahn 算法,可分为如下几步:

  1. 计算所有结点的入度,并将入度为 0 的放入一个队列
  2. 取出队列中第一个元素,将其输出后删除(使其相邻结点入度减一)。如果其相邻结点入度更新后为 0 ,则将其放入队列
  3. 重复 2 直到队列为空。如果输出数量与结点数量不符则说明图中存在环。

由于每次都是处理当前结点的邻接,所以是广度优先。算法之所以正确是因为,入度为 0 即代表该节点没有前驱结点,那么该结点可直接进行,那么每次只需要输出没有前驱的结点。对于邻接结点更新后入度变为 0 说明其前驱都已访问完毕,该节点可以访问了,那么可以将其输出,如此反复。

由于图算法与图本身实现有较大关联,代码并不具有通用性,所以这里给出Java实现的链接供参考。

图自算法导论

Gif 根据visugo.net 制作