每周学点大数据 | No.31拓扑排序

No.31期

拓扑排序

Mr. 王：很好，你还记得这个问题。接下来我们来讨论另一种磁盘中的大数据算法策略，叫作时间前向处理方法。在这种策略中，我会讲解求解最大独立集的方法。先介绍一个时间前向独立集的其他例子。

这是一个DAG。所谓 DAG 就是有向无回路图。在 DAG 中的每一条边都是有方向的，但是 DAG 中不允许有环形的回路。

这个DAG 比较特殊，它的每一个源点，也就是没有指向它的边的节点都有一个逻辑变量值 0 或者 1。所有的中间节点上都有一种逻辑运算，其中 ∧是与运算， ∨是或运算。逻辑运算的计算方法你应该比较清楚了。在这个 DAG 中，我们希望求解所有的点上代表的逻辑变量值。比如某一个顶点 v 上面的运算是与运算，而指向它的两个逻辑变量值均为 1，那么顶点 v 所代表的逻辑变量值就是 1。依此类推。

解决这个问题的关键之一是，我们必须要知道按照什么顺序来计算这些点的逻辑变量值。如果当我们要计算一个点的值时，它的两个输入的值还没有求出来，那么这个点的值就无法求出来，需要等待前面的节点的值。所以，我们要先理解一个内存算法，叫作拓扑排序。

小可： 拓扑排序？

Mr. 王：是的，拓扑排序是一个非常经典的图算法，适用于 DAG，将 DAG 转化为一个序列。

首先我们来谈谈什么是拓扑排序。 你听说过课程网络图吧？

小可： 就是描述那些课程前置关系的有向图。比如要想学高等数学，就应该先学初等数学。在课程网络图中，就画一条有向边，由初等数学指向高等数学。

Mr. 王：嗯，这条边也就描述了两门课程的先后关系。在实际生活中，类似课程网络图这种具有先后关系的例子是非常多的。在课程网络图中，也经常会出现一些比较复杂的情况，比如两门课程同时是第三门课程的前置课程，如“ C 语言程序设计”和“计算机数学基础”这两门课程，都是“数据结构与算法”这门课程的前置课程。在实际的课程图中，这个网络会变得非常的庞大且复杂。这种网络也叫作 AOV 网。

小可：什么是 AOV 网？

Mr. 王：所谓AOV 网（Activity-On-Vertex network），就是顶点活动网。在这种网络中，我们用节点来代表一个活动（Activity），用有向边来表示它们之间的前置关系。在课程网络图中，这个Activity 代表的就是课程，它用图中的节点来表示，而用有向边来表示课程中的前置关系。比如有两个节点 A、 B，如果有一条边 (A,B) 就说明A 必须在 B 之前执行，或者说仅当 A 执行过之后， B 才能执行。 AOV 网具有这样一个特点，就是它是一个 DAG，也就是有向无回路图。

小可：嗯，如果有回路就不对了，“后面”的课程不可能重新成为“前面”的课程的前置。

这是符合逻辑的。

Mr. 王：没错，在 AOV 网中，就有一个关于你说的“前面”和“后面”的问题。我们想要排出一个各项任务的执行序列，也就是在实际的执行过程中，这些活动到底谁先执行，谁后执行，同时要使得它们不违背AOV 网所描述的前置关系。这项工作就叫作拓扑排序。

小可：在课程网络图中，求拓扑排序就相当于排出一个课程的顺序表吧，就是我先上哪一门课，再上哪一门课。这就像是通过课程网络图来编写课程培养计划一样。

Mr. 王：没错，现在我们来形式化这个问题。拓扑排序就是将像 AOV 网这样的 DAG 转换成一个线性序列，使得如果 AOV 网中存在一条边 (a,b)，那么在形成的这个线性序列之中， a 就要出现在 b 的前面。

小可：这个问题还真的很有意义，可以用来排前面提到的课程顺序表。那么这个问题怎么解决呢？

Mr. 王：其实有一个非常简单易行的算法可以解决这个问题。

每一轮的迭代只需要完成三项工作 ：

第一， 找到一个没有入度的顶点。

第二， 将它插入到拓扑序列中。

第三， 将它和它所有的出度从 AOV 网中删除。

小可：就这么简单？

Mr. 王：没错，就是这么简单。我们可以用刚才的图来举例。响其后置活动的执行。比如学过了“计算机数学基础”和“ C 语言程序设计”，就可以学习“数据结构与算法”了，所以我们可以将加入了拓扑序列的那些节点的出度删除，然后这个节点也就没用了，同样删掉。

小可：于是就会有更多的节点“露”出来，没有了入度，它们就可以被加入到拓扑序列中。我懂了，这个步骤可以持续执行下去，直到所有的活动都被加入到拓扑序列中。可是在每一个步骤中，如果发现有两个节点都没有入度怎么办呢？

Mr. 王：这种情况也是普遍存在的，在这种情况下任选一个或者取 ID 较小的那个节点就可以了。因为选择任何一个节点都不会破坏拓扑序列满足 AOV 网的要求。但这也意味着，拓扑序列是不唯一的。

小可：嗯，我懂得拓扑排序了。

内容来源：灯塔大数据