数据结构（50）有向无环图和AOV网的拓扑排序

目录

1、有向无环图

2、拓扑序列

---

1、有向无环图

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式

((a+b)*(b*(c+d) + (c+d)*e) * ((c+d)*e)*((c+d)*e)

可以用二叉树来表示，如图50-1所示

                      图50-1  二叉树描述表达式

仔细观察上述表达式，可发现有一些相同的子表达式(c+d)和(c+d)*e。

若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间，图50-2所示为该表达式的有向无环图表示

             图50-2  有向无环图描述表达式

2、拓扑序列

AOV网（Activity On Vertex Network，顶点表示活动的网）：若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，记为AOV网。在AOV网中，活动Vi是活动Vj的直接前驱，活动Vj是活动Vj的直接后继，这种前驱和后继关系具有传递性，且任何活动Vi不能以它自己作为自己的前驱或后继。

拓扑排列：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑序列：

①每个顶点出现且只出现一次。

②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。

或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

①从AOV网中选择一个没有前驱的顶点并输出。

②从网中删除该顶点和所有以它为起点的有向边。

③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

先介绍一个不存在环的拓扑排序：

再介绍一个存在环的 ：

 

由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为O(|V|+|E|)。

深度优先遍历也可实现拓扑排序。

对于一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序：

①从AOV网中选择一个没有后继（出度为0）的顶点并输出。

②从网中删除该顶点和所有以它为终点的有向边。

③重复①和②直到当前的AOV网为空。

用拓扑排序算法处理AOV网时，应注意以下问题：

①入度为零的顶点，即没有前驱活动的或前驱活动已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。

②若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。

③由于AOV网中各顶点的地位平等，每个顶点编号是人为的，因此可以按照拓扑排序的结果重新编号，生成AOV网的新的邻接矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，其邻接矩阵是三角矩阵，则存在拓扑序列，反之则不一定成立。

印证了上面那句话：

邻接矩阵是上三角矩阵，则存在拓扑序列

邻接矩阵是非上三角矩阵，则可能存在拓扑序列，也可能不存在拓扑序列