[图](10)拓扑排序

有向无环图及其应用

一个无环的有向图称作有向无环图(directed acycline graph)，简称DAG图，DAG图是一类较有向图更一般的特殊有向图，如下图所示：

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

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

可以用二叉树来表示，如下图所示：

仔细观察该表达式，可发现一些相同的子表达式，如(c+d)和(c+d)*e等，在二叉树中，它们也重复出现，若利用有向无环网，则可实现对相同子式的共享，从而节省存储空间，如下图为表示同一表达式的有向无环网：

检查一个有向图是否存在环要比无向图复杂，对于无向图来说，若深度优先遍历过程中遇到回边(即指向以访问过的顶点的边)，则必定存在环，而对于有向图来说，这条边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧

但是，如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边(如下图所示)，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和u的环

有向无环图也是描述一项工程或系统的进行过程的有效工具，除最简单的情况之外，几乎所有的工程(project)都可分为若干个称做活动（activity)的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后

对整个工程和系统，人们最关系的就是两个方面的问题：一是工程能否顺利进行，二是估算整个工程完成所必须的最短时间，对应于有向图，及为进行拓扑排序和求关键路径的操作。

拓扑排序

对于任何有向图而言，其拓扑排序为其所有结点的一个线性排序（对于同一个有向图而言可能存在多个这样的结点排序）。该排序满足这样的条件——对于图中的任意两个结点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。

拓扑排序主要用来解决有向图中的依赖解析（dependency resolution）问题。

举例来说，如果我们将一系列需要运行的任务构成一个有向图，图中的有向边则代表某一任务必须在另一个任务之前完成这一限制。那么运用拓扑排序，我们就能得到满足执行顺序限制条件的一系列任务所需执行的先后顺序。当然也有可能图中并不存在这样一个拓扑顺序，这种情况下我们无法根据给定要求完成这一系列任务，这种情况称为循环依赖（circular dependency）。

为什么会有拓扑排序？拓扑排序有何作用？

举个例子，学习java系列的教程

就比如学习java系类(部分)从java基础，到jsp/servlet，到ssm，到springboot，springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础和html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么，这个学习过程即构成一个拓扑序列。当然这个序列也不唯一，你可以对不关联的学科随意选择顺序(比如html和java可以随便先开始哪一个。)

那上述序列可以简单表示为：

其中五种均为可以选择的学习方案，对课程安排可以有参考作用，当然，五个都是拓扑序列。只是选择的策略不同！

AOV网

AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动图，简称（AOV)网，其全称为(Activity On Vertex Network)

AOV网特点：

• AOV网中的弧表示活动之间存在的某种制约关系
• AOV网中不能出现回路
  • 若AOV网中出现回路，则代表其工程优先关系混乱

拓扑序列：

设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,...,vn称为一个拓扑序列，当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前

拓扑排序(Topological Sort)：

对一个有向图构造拓扑序列的过程称为拓扑排序

• 拓扑排序使得AOV网中所有应当存在的前驱和后继关系都能得到满足

其图解如下所示：

基本思想：

• 从AOV网中选择一个没有前驱的顶点并且输出
• 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧
• 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点

数据结构：

图的存储结构采用邻接表存储，在顶点表中增加一个入度域in，其作用是对该顶点的入度边进行计数：

采用栈或队列存储所有无前驱的结点，为了不影响其后续的操作，在 [ 删去顶点所关联的出度边 ] 的时候，我们只操作 in 当中的数值，不改变其原本的逻辑结构，如下所示：

拓扑排序伪代码如下所示：

1.栈S初始化：累加器count初始化
2.扫描顶点表，将没有前驱(in域为0)的顶点压栈
3.当栈非空时循环
   3.1.弹出栈顶元素，输出，累加器加1
   3.2.将弹出顶点的各个邻接点入度域减一
   3.3.将新的入度域为0的顶点入栈
4.if(count<vertexNum) 输出由回路的信息(当栈空时，若未输出全部顶点，则代表图中存在回路，以为有回路的存在，则已不存在无前驱的顶点)

算法如下所示：

Status TopSort(ALGraph* G) {
    //拓扑排序
    int* Stack = (int*)malloc(sizeof(int) * G->vexnum);//栈作为记录入度量为0的顶点
    int top = -1;
    int count = 0;//累加器
    for (int i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].in == 0) {
            top++;
            Stack[top] = i;//记录其顶点序号
        }
    }
    int OutVex, InVex;
    while (top != -1) {
        OutVex = Stack[top--];//出度边等于栈顶元素，按照其约定，需要删去其所有出度边

        p = G->vertices[OutVex].firstarc;
        printf("%d ", G->vertices[OutVex].data);//打印顶点，打印其拓扑序列
        while (p) {
            InVex = p->adjvex;
            G->vertices[InVex].in--;//不改变其逻辑结构，为拓扑排序只改变其入度量
            if (G->vertices[InVex].in == 0) Stack[++top] = InVex;
            p = p->nextarc;
        }
    }

    if (count < G->vexnum) {
        printf("存在回路\n");
        return ERROR;
    }

    return OK;
}

本文链接：