什么是拓扑排序?
答:拓扑排序是由某个集合上的偏序得到该集合上的一个全序的操作。实际上是对邻接表表示的图进行深度优先遍历的过程。
AOV网
用顶点表示活动,用弧表示活动间的优先关系的有向图。
AOV网中不允许有回路
拓扑排序——把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
检测AOV中是否存在环:
对图进行拓扑排序,若网中的左右顶点都在拓扑有序序列中,则无环,否则有环。
拓扑排序的方法
- 需用到邻接矩阵和链栈
1.为顶点个数为n的有向图建立一个邻接矩阵
2.再建立一个含有顶点元素和出度的结构体数组s
3.遍历邻接矩阵,得到每一个元素的入度,给数组s赋值
4.寻找数组s中出度为0的顶点的序号i(从1开始),设链栈的顶层指针为top。当找到第一个入度为0的顶点,做以下的操作:
s[i].indegree = -1; //作为链栈的结尾
top = i; //将该顶点的数组下标给top,表示链栈入口
若有不止一个入度为0的顶点,于是重复以下:
s[i].indegree = top; //入栈
top = i;
5.当所有入度为0的顶点入栈完毕,出栈top的元素,并且要删除有向图上以该顶点元素为起点的所有弧,等同于在本存储结构中给邻接矩阵上该顶点所在的行的非零元素分赋 0(删除弧),并且分别对每条删除的弧的终止顶点所在数组的入度减去1。若这些顶点的入度减1后为0,则返回执行步骤4。
6.最后,当top地址为-1,以为着链栈为空,顶点全部出栈,拓扑排序完成。