问题 单项选择题

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

A.包含回路

B.是强连通图

C.是完全图

D.是有向树

答案

参考答案:A

解析:

本题考查拓扑排序的概念。

对一个有向无环图(Directed Acyclic Graph,DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若〈u,v〉∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列。需要注意的是:①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的;②若图中存在有向环,则不可能使顶点满足拓扑次序;③一个DAG的拓扑序列通常表示某种方案切实可行。由注意的第②点知,本题正确答案为A。

选择题
单项选择题