当前课程知识点：数据结构 > 第6章 图 > 6.5 拓扑排序 > 讲解
本节，我们来学习图的另外一类应用，拓扑排序
我们先来看一个概念
AOV网
所谓AOV网，就是Activity On Vertex
顶点代表活动，在现实世界当中，有一些流程
我们可以用
AOV网来描述
比如，这个表给出了一些课程之间的先修、后修关系
如果我们把它抽象成AOV网
可以是这样的一个有向图
这里的箭头表示
箭头端指向的课程，如果要开设
先得学习箭尾端指向的课程
比如，4这个课程，数据结构
它要求先学
2、3这两门课程
因为，有两条弧是以4为弧头的
也就是2、4和3、4
这两条边
那么
它们分别对应着C语言和离散数学
学习数据结构之前
我们要把这两门课学了，才能去学数据结构
这就是AOV网，第二个概念
拓扑排序，拓扑排序可以用来干什么呢
它可以把顶点集合的偏序转成全序，偏序和全序
是离散数学当中的概念
说得更通俗一点，就是将有向图当中的全部顶点
按照先后关系来排列
注意，是顶点的先后关系
而不是大小关系
比如刚才
这样一个描述课程之间的先修后修关系的有向图
我们对它进行拓扑排序，可以得到这样一个序列
这个序列，比如4
在它之前，一定有2和3，在3之前一定有2
因为，3这门课要先学习2这门课
总之
我们把有向图当中的多个顶点，排成了一个序列
用来描述这多个顶点
在有向图当中的先后关系
很显然
拓扑排序可能不唯一
比如
1、2这两门课
它们是没有先修课程的
这两门课，先学谁都可以
也就是说
第一个顶点
可以是2
后面可以是1，从这个例子看
拓扑排序可能不唯一
拓扑排序到底有什么用呢
拓扑排序可以用来检测一个有向图是否包含环
如果一个有向图不包含环
该图叫做DAG
也就是有向无环图
拓扑排序可以用来检测
AOV网是否包含环
因为，我们知道
如果一个
描述课程先修后修关系的有向图
如果包含环
那意味着，这个流程是不合理的
比如，我们在7到3，加一条边
这样，3、4、7这三门课就没法开设了
因为
这3个顶点之间出现了一个环
这三门课，到底先开哪一门呢
没法开
因为，每一门课都是其它课的先修课程
这时候的AOV网是不合理的
利用拓扑排序，可以用来检测是否包含环
现在，我们来看拓扑排序具体的算法
首先，找到一个入度为0的顶点v，输出之
入度为0
如果没有这样的顶点
那么，算法就结束了
就说明图包含环
比如，下面这样一个有向图
2这个顶点是没有入度的
它的入度为0
没有边指向2
所以，我们直接输出它
然后，删除v及其关联的弧
刚才输出了2，就把2这个顶点和2出来的这些边，全删掉
重复刚才的过程，直到输出图当中所有的顶点
如果所有的顶点都输出了
说明
AOV网是没有环的
也就是，它是一个DAG(有向无环图)
输出2之后
重复刚才的步骤
现在，4这个顶点的入度为0，输出，删掉
然后，0这个顶点的入度为0，输出，把边删掉
1和3这两个顶点
它们的入度都是0
随便选一个
刚才我们说了，拓扑排序可能不唯一，假设我们输出3
然后删掉，下一个入度为0的是1，输出
把边、顶点删掉
最后一个5，输出
图当中所有的顶点都输出了
说明，我们给出来的那个AOV网，是合理的
是没有环的
现在，如果在这个图上加一条边
比如，我们在3到4之间加一条边
这时候，图是包含环的
现在，我们再对它进行拓扑排序
先找入度为0的，2
删掉相应的边
然后你会发现，剩下的5个顶点，入度都不为0
这时候，就找不到入度为0的顶点了
这时候，就应该退出了
因为，还没有输出
图当中所有的顶点，说明图是包含环的
接下来，我们看看拓扑排序
它的具体实现
我们对以邻接矩阵存放的图G，进行拓扑排序
用第二个参数(是一个int型指针)
实际上，是一个int型的数组
用它来存放最终得到的拓扑序列
因为，我们会修改里面的元素
所以，它是带了引用参数的
返回值是int型
表示什么意思呢
如果我们进行排序的图是无环的
也就是，是一个DAG
那我们返回一个1
否则(它包含环)
我们返回0，用返回值来代表是否包含环
我们初始化了一个队列Q，这个Q是用来干什么的呢
在某一个时刻
假设图当中包含多个顶点的入度是0
我们应该将这多个入度为0的顶点，放到一个队列里面
将它们暂存起来
从这个角度说
队列完全是为了暂存那些入度为0的顶点
也就是，把队列当做一个容器
既然当做一个容器
不用队列也可以
比如用栈也可以
只要它能存若干个顶点，就可以了
紧接着，有一个伪码
calcIndegrees，这个伪码很容易理解
它是计算、统计
图G当中，所有顶点的入度，很明显
第二个参数
indegrees
应该是一个数组
接着，我们去扫描这个数组
看哪些顶点
它们的入度是0
只要入度为0
就将这些顶点入到队列Q当中
这也验证了刚才Q的作用
存放所有入度为0的顶点
接下来，我们为第二个存放拓扑序列的参数
分配内存，因为最终情况下，这个拓扑序列
它的长度，就是顶点个数
我们分配顶点个数个元素
每个元素都是int型的
然后，有个计数器count，用来统计当前我们输出了多少个顶点
很明显
如果这个count的值，没有被自增到顶点个数
说明图是包含环的
while循环，继续循环的条件是Q非空，队列当中存放了入度为0的顶点
我们就从队列当中，取出队头
也就是，第一个入度为0的顶点
将它输出
当然
这里出队了之后，队头元素v
我们并没有真正地输出
只是把它记录到第二个参数里面
大家看到，这个count采用的是后置的自增
那意味着，我们输出的第一个顶点
我们要输出的第一个顶点，是放到0位置的
因为，count的初值是0
我们把v，放到topo[count++]这个元素里面
所以，topo这个数组，就是存放拓扑序列的
现在
我们开始内层循环
输出了入度为0的顶点之后
我们要去把顶点v，以及从v出来的边，都删掉
那怎么实现这个操作呢
在纸上
你可以直接把v和v出来的那些边删掉
但我们写程序，如何在内存当中删呢
实际上，我们根本就不需要删
我们只需要看，从v出来了哪些边
然后，把那些边到达的顶点
它们的入度减一个1，就可以了
也就是说，把它们到达的顶点的入度
减了1
我们做删除
修改的矩阵当中的元素(下标)是v、w
别忘了，图是采用邻接矩阵，来存放的
到达w的那些边
它们对应的元素，应该是edges[v][w]，w是作为列下标的
如果v到w有边
我们就把它到达的那个顶点w，将它的入度减一个1
大家看到，这里是前置的自减
判断减1之后的值，是否为0
就相当于，你把v以及v到达的那个顶点w
把它的入度减1了
相当于，把这条边删掉了
别忘了，前置的自减，减1之后，再去判断是否为0
如果入度为0
新的w的入度是0
那么，就把w入队
跟我们刚才讲的一致
用Q来存放所有入度为0的顶点
这个while循环结束了之后
如果count被自增到了顶点个数，注意，这是关系等
如果它们二者相等
那说明，图是没有环的
如果它们不相等，count小于顶点数
说明，图是有环的
这个算法的时间复杂度，也跟我们刚才讲的
图的遍历，是一样的
邻接矩阵，时间复杂度是O(n^2)
邻接表，是O(n+e)
因为，无论怎么样
这个算法要将邻接矩阵当中的每一行、每一列都扫描一遍
而邻接表
有n个链表，n个头结点
这n个链表当中
一共有e个结点，都会扫描一遍
所以是n+e
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
