问题 单项选择题

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

A.包含回路

B.是强连通图

C.是完全图

D.是有向树

答案

参考答案:A

解析:

本题考查拓扑排序的概念。对一个有向无环图(DirectedAcyclicGraph,DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(TopologicalOrder)的序列,简称拓扑序列。需要注意的是:

①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的;

②若图中存在有向环,则不可能使顶点满足拓扑次序;

③一个DAG的拓扑序列通常表示某种方案切实可行。由注意的第②点可知,本题正确答案为A。

解答题
单项选择题