拓扑排序什么是逆拓扑排序

拓扑排序和冒泡排序的区别是什么

冒泡排序是一种交换排序方式。

设有n个数据依次放在数组元素a(1)至a(n)中，用冒泡法对这n个数据进行递增排序的过程为：先比较a(1)与a(2)，若逆序则交换之，接着比较a(2)与a(3)，若逆序就交换……依次进行，知道将a(n-1)与a(n)比较交换完，才算完成...

数据结构拓扑排序

拓扑排序说白了就是依次遍历没有前驱节点的节点。

分析：这6个节点中，最早是0没有前驱，所以先遍历0； 去掉0节点和他的指针向量后，发现1和5都没有前驱，这个时候看你的程序怎么写了，不过就此题来说，你可以随便取一个，1也行，5也行，我先取1吧； 去掉1和他的指针向量，发现2和5都没前驱，同上，我选2； 照上面一次做下去，最后得到： 0-1-2-3-5-4 当然：0-1-5-2-3-4 0-1-2-5-3-4 0-5-1-2-3-4 也都对。

数据结构 拓扑排序

【1】拓扑排序 在一个表示工程的有向图中，有顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。

AOV网中的弧表示活动之间存在的某种制约关系。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

【2】拓扑排序算法 对AOV网进行拓扑排序的基本思路： 从AOV网中选择一个入度为0的顶点输出； 然后删除此顶点，并删除以次顶点为尾的弧； 继续重复此操作..... 直到输出全部顶点或AOV网中不存在入度为0的顶点为止。

由于拓扑排序过程中，需要删除顶点，显然用邻接表更加方便。

因此我们需要为AOV网建立一个邻接表。

另外，考虑到算法过程中始终需要查找入度为0的顶点？ 需要在原顶点表节点结构中，增加一个入度域in，in就是入度数字。

什么是逆拓扑排序

具体算法描述如下： 1． 输入e条弧，建立AOE-网的存储结构。

2． 拓扑排序，并求得ve[]。

从源点V0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。

如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。

3． 拓扑逆序，求得vl[]。

从汇点Vn出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。

4． 求得关键路径。

根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。

若某条弧满足条件e(s) = l(s)，则为关键活动。

为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中，增设一个栈，以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列。