题14

题14

题目

下列关于拓扑排序的说法中, 正确的是 ( ).
I. 强连通图不能进行拓扑排序
II. 在一个有向图的拓扑序列中，若顶点 在顶点 之前，则图中必有一条弧
A. 仅 I
B. 仅 II
C. I 和 II
D. 都不正确

分析

强连通图是针对有向图的概念，是说图中任意两个顶点都是相互可达的，所以强连通图一定不能进行拓扑排序，因为拓扑排序是对有向无环图的操作，要是互相连通的话，就会有环。

解

A
强连通图是指有向图中任意顶点对之间都存在两条相反的路径, 这意味着强连通图中一定存在环,因此不能进行拓扑排序,I 正确。
假设顶点 和 的入度均为 0,且分别有两条孤从 和 指向同一顶点 ,则产生的拓扑序列可以是 ,但是此时并无一条弧 ,II 错误。