C＋图系列之有向无环图的拓扑排序算法

1. 前言

有向无环图，字面而言，指图中不存在，意味着从任一顶点出发都不可能回到顶点本身。有向无环图也名为 。

有向无环图可用来描述顶点之间的关系，依赖这个概念在面向对象编程中经常出现。如使用组件时，需要先有组件，或说组件依赖组件，通俗言之，有才有。可用如下图描述。

在面向对象编程的场景中，组件之间的依赖关系链中不能出现环。如现有 个组件，依赖，依赖于。正确的图解应该如下图。

如果在 和添加依赖，则会出现环，在面向对象中，称此种情况为循坏依赖，显然，会导致死锁，从而让程序崩溃。

如下图所示，如果图结构是用来描述面向对象中组件之间的依赖关系，则会出现逻辑悖论：

图示有才有、有 才有，有才有 。

这里就出现了先有鸡还是先有蛋的悖论问题。因为图中出现了 依赖自己了的矛盾。

下文将深入讲解有向无环图的特点及应用。

2. AOV 网

任何的必须是特定应用场景下的语义描述，有向无环图也仅用顶点之间不能有环的场景之下。

如下图，使用有向无环图描述面向对象中组件的依赖关系，顶点与顶点之间的边（弧）描述了顶点（组件）间的制约关系。因有特定的语义环境要求，故，图中不能出现环。

常用于描述或的内部组织结构。

现实生活中，一个工程（系统）可分解成诸多子工程（系统），且子工程之间存在彼此制约现象，即某一个子工程需要等待另一个子工程或多个子工程完成后方能进行，也可称为同步（前一个子工程的结束是后一个子工程的开始的前置条件）。当然，也会有些子工程是不依赖任何其它子工程，可称为异步（多个子工程可以同时进行）。

称遵循这种逻辑关系而构建的有向无环图为 网。

在 网中：

若从顶点 到顶点 之间存在一条有向路径，称顶点 是顶点 的前驱。或称项点 是顶点的后继。

若是图中的弧（子工程之间的制约关系），称顶点 是顶点的直接前驱，顶点 是顶点的直接后继。

当然，在网中，人们关心的有 点：

工程能否顺利完成。即在设计分解子工程时，子工程之间的依赖顺序是否正确。

整个工程完成所需要的最短时间是多少。

这也是有向需要提供的核心逻辑功能。

2.1 拓扑排序

网这种逻辑结构在现实生活中比比皆是，如某个课程可以分成很多章节独立的知识块，其中一些知识块必需以另外一些知识块为前置条件。

如学习的知识时需要有，同时也需对有所了解。而又需要有和为前提条件。除数据库外，所有知识需要有面向对象知识为前提条件。如下图所示：

如何检查上图结构的正确性？

衡量网结构正确性的标准是必须保证 网中不能出现回路，否则会出现自己依赖自己的悖论。

可以使用拓扑排序算法验证 网结构的合理性。

拓扑排序算法的思想：

这里的排序并不是指递增或递减式的排序，而是通过算法把有向无环图中的顶点以线性序列方式输出。如果网中的所有顶点都出现在它的线性序列中，则说明此 网不存在环，或说拓扑排序算法可以检查图是否有环。

一定要知道，针对于网，拓扑排序的线性序列并不是唯一的。

对上图知识之间的图，其拓扑排序的流程如下：

从网中选择一个没有前驱或说入度为的顶点。图中有和  个顶点可以选择。因拓扑排序的结果不是唯一的，出现同时多个可选顶点时，可自义优先级选择策略（如按顶点的编号顺序或字符串的字典顺序）。这里选择顶点。

从图中移出顶点，且删除与此顶点有关联的。

继续选择入度为 的顶点。可供选择的有个顶点。这里选择线程，并删除与线程有关联的边。

Tip：当同时可供选择的顶点为多个，说明，此时顶点所代表的任务之间没有互相制约关系。所以，无论先执行哪一个任务都不会影响最终结果。

重复上述逻辑，直到图中所有顶点均被选择出来。如下图是拓扑排序算法的选择顺序之一。注意，顺序不是唯一的。

如果图中所有顶点都出现在线性序列中，则说明，图中知识之间的逻辑依赖关系是健康的（没有回路），否则表示网的设计有问题。

拓扑排序算法并不关心最终顶点输出的顺序，仅在意是否能让所有顶点以线性方式输出。所以，拓扑排序即可以借助于队列也可以使用栈存储入度为 的顶点。

2.2 拓扑排序的实现

图的关系描述可以使用和。本文将使用邻接矩阵的存储方式实现拓扑排序算法。

2.2.1 邻接矩阵

使用存储图中顶点的关系，可以很容易查询到与某个顶点的和数量。

以某个的编号为，与此行相交列中有值的单元格数量即为此顶点的出度数量。如下图，在网中，可认为有另 个顶点依赖此顶点。

以某个顶点的编号为列号，与此列相交行中有值的单元格数量为此顶点的入度数量。如下图，可认为编号为 的顶点依赖另 个顶点。

利用邻接矩阵的上述特点，可服务于拓扑排序中查找入度为 的顶点。

顶点类型：

网类型：除了提供基本，主要是实现。

类中函数功能介绍：

函数：可以按顶点的值或编号查找。

函数：创建新顶点。

函数：添加顶点之间的关系。

拓扑排序：核心代码。

测试：

输出结果： 拓扑排序后，显示顶点关系时，可看到关系信息已经全部被抹去。

3.总结

邻接表的底层逻辑和邻接矩阵是没有差异性的。区别在于，存储方式的不同，对查找入度为 的顶点的逻辑不同。

在邻接表中查找顶点的出度数量较方便，为了提高查找入度量的性能，在设计顶点类时，可以添加一个入度域，用来记录入度的数量。

受限篇幅，基于邻接表的拓扑排序以及的相关知识在下一章节中讲解。