题13

题13

题目

Q:下列关于拓扑排序的说法中, 错误的是 ( ).
I. 若某有向图存在环路, 则该有向图一定不存在拓扑排序
II. 在拓扑排序算法中为暂存入度为零的顶点, 可以使用栈, 也可以使用队列
III. 若有向图的拓扑有序序列唯一, 则图中每个顶点的入度和出度最多为 1
IV. 若有向图的拓扑有序序列唯一, 则图中入度为 0 和出度为 0 的顶点都仅有 1 个
A. I、III、IV
B. III、IV
C. II、IV
D. III

分析

A:说法1的描述本身是正确的，题目要选的是描述错误的，别看错了

解

D
对于 ,若有向图中存在环,运行拓扑排序算法后,肯定会剩下有环的子图,在此环中无法再找到入度为 0 的顶点, 拓扑排序也就无法再运行。
对于 II, 若两个顶点之间不存在祖先或子孙关系, 则它们在拓扑序列中的前后关系是任意的, 因此使用栈和队列都可以, 因为进栈或队列的都是入度为 0 的顶点。
III 是难点, 若拓扑序列唯一, 则很自然联想到一个线性的有向图, 下图的拓扑序列也唯一, 但却不满足该条件。
对于 IV, 若入度为 0 的顶点不唯一, 则这些顶点均可作为拓扑序列的起点;
若出度为 0 的顶点不唯一, 则这些顶点均可作为拓扑序列的终点。