拓扑排序
标签: 数据结构
学习人数: 6509


全屏播放
赞赏支持

有向无环图(DAG)
  如果一个有向图不存在环,也就是任意结点都无法通过一些有向边回到自身,那么称这个有向图为有向无环图。

 

AOV网络
  在有向图中,用顶点表示活动,用有向边<Vi,Vj>表示活动 i 是活动 j 的必须条件。这种有向图称为用顶点表示活动的网络(Active on vertices),简称AOV网络。 
在AOV网络中,如果活动Vi必须在Vj之前进行,则存在有向边<Vi,Vj>,并称Vi是Vj的直接前驱,Vj是Vi的直接后继。这种前驱与后继的关系具有传递性和反自反性,这要求AOV网络中不能出现回路,即有向环。因此,对于给定的AOV网络,必须先判断它是否存在有向环。

 

拓扑排序
  检测有向环可以通过对AOV网络进行拓扑排序,该过程将各个顶点排列成一个线性有序的序列,使得AOV网络中所有的前驱和后继关系都能得到满足。 如果拓扑排序能够将AOV网络的所有顶点都排入一个拓扑有序的序列中,则说明该AOV网络中没有有向环,否则AOV网络中必然存在有向环。AOV网络的顶点的拓扑有序...

登录查看完整内容


课后作业

课后习题

 

【2018年真题】下列选项中,不是如下有向图的拓扑序列的是()

A. 1, 5, 2, 3, 6, 4    B. 5, 1, 2, 6, 3, 4
C. 5, 1, 2, 3, 6, 4    D. 5, 2, 1, 6, 3, 4

参考答案:D

 

【2016年真题】若将n个顶点e条弧的有向图采用邻接表存储,则拓扑排序算法的时间复杂度是()
A.O(n)        B.O(n+e)        C.O(n2)        D.O(n*e)

参考答案:B

 

【2014年真题】对如下所示的有向图进行拓扑排序,得到的拓扑序列可能是() 

A.3,1,2,4,5,6 
B.3,1,2,4,6,5 
C.3,1,4,2,5,6 
D.3,1,4,2,6,5

参考答案:D
答案解析:按照拓扑排序的算法,每次都选择入度为 0 的结点从图中删去,此图中一开始只有 结点 3 的入度为 0;删掉 3 结点后,只有结点 1 的入度为 0;删掉结点 1 后,只有结点 4 的 入度为 0;删掉 4 结点后,结点 2 和结点 6 的入度都为 0,此时选择删去不同的结点,会得出不同的拓扑序列,分别处理完毕后可知可能的拓扑序列为 314265 和 314625,选 D。 

 

【2012年真题】若用邻接矩阵存储有向图,矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是()。 
A.存在,且唯一 
B.存在,且不唯一 
C.存在,可能不唯一 
D.无法确定是否存在 

参考答案:C

答案解析:考查拓扑排序、与存储结构和图性质的关系。 

对角线以下元素均为零,表明该有向图是一个无环图,因此一定存在拓扑序列。对于拓扑序列是否 唯一,我们试举一例:设有向图的邻接矩阵,则存在两个拓扑序列。所以该图存在可能不唯一的拓扑排序。 

结论:对于任一有向图,如果它的邻接矩阵中对角线以下(或以上)的元素均为零,则存在拓扑序列(可能不唯一)。反正,若图存在拓扑序列,却不一定能满足邻接矩阵中主对角线以下的元素均为零,但是可以通过适当地调整结点编号,使其邻接矩阵满足前述性质。 

 

【2011年真题】下列关于图的叙述中,正确的是()
Ⅰ. 回路是简单路径 
Ⅱ.存储稀疏图,用邻接矩阵比邻接表更省空间 
Ⅲ.若有向图中存在拓扑序列,则该图不存在回路 
A.仅Ⅱ
B.仅Ⅰ、Ⅱ
C.仅Ⅲ
D.仅Ⅰ、Ⅲ 

解答:C。Ⅰ.回路对应于路径,简单回路对应于简单路径;Ⅱ.刚好相反;Ⅲ.拓扑有序的必要条件。故选C。 

 

【2010年真题】对下图进行拓扑排序,可以得到不同的拓扑序列的个数是()。 

A.4         B. 3         C.2         D.1

参考答案:B
答案解析:考查拓扑排序序列。 
题中图有三个不同的拓扑排序序列,分别为 abced,abecd,aebcd。 


登录后发布评论

暂无评论,来抢沙发