数据结构-拓扑排序

题目：对下面有向图进行拓扑排序，得到的拓扑序列可能是（）

数据结构-拓扑排序

选择D

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

（1）每个顶点出现且只出现一次

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

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

拓扑排序的时间复杂度为:O(V+E)

对于一般的图来说，若其邻接矩阵表示方法为三角矩阵，则存在有序拓扑排序序列，反之不一定成立。[若为三角矩阵，则有向图肯定没有环]

若有向图不能写成拓扑序列，那么存在有向图存在环。即拓扑排序可以检验有向图是否存在环。

求解拓扑排序的算法流程：

（1）写出各结点的入度，将入度为0的点，作为初始点。

（2）删除（1）中的入度为0的点，并将以结点为起始边去掉，继续写出剩余各节点的入度。

（3）重复（1）（2）步骤，直至结束。结束存在两种情况：没有结点或者 不存在结点入度为0的结点 ->>有向图存在环。

注意点：可能存在多个入度为0的点，这种情况，拓扑排序序列就不唯一。

上面的题的过程：

数据结构-拓扑排序

逆拓扑排序：

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

（2）从网中删除该顶点和以它为终点的有向边

（3）重复（1）（2）直至AOV网为空。