软件设计师试题解析：拓扑排序是指有向图中的所有顶点排成一个线性序列的过程

信管网考友

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定 （ ） 。

A、包含回路

B、是强连通图

C、是完全图

D、是有向树

信管网考友

这个题怎么选

信管网考友

A

信管网考友

B

信管网考友

A

信管网参考答案: A(仅供参考,欢迎评论交流)

信管网解析:

解析:对有向图进行拓扑排序的方法如下:

(1 )在AOV网中选择一个入度为0 (没有前驱)的顶点且输出它。

(2)在网中删除该顶点及其与该顶点有关的所有边。

(3)重复以上步骤,直至网中不存在入度为0的顶点为止。

执行结果会有两种情况：一种是所有顶点已输出，此事整个拓扑排序完成，说明网中不存在回路；另一种是尚有未输出的顶点，剩余的顶点均有前驱顶点，表明网中存在回路，拓扑排序无法进行下去。