以下关于拓扑排序的说法中错误的是（）。I 如果某有向图存在环路 则该有向图一定不存在拓扑排序I
拓扑,环路,说法
已帮助 人
以下关于拓扑排序的说法中错误的是（）。I，如果某有向图存在环路，则该有向图一定不存在拓扑排序II，在拓扑排序算法中，为暂存入度为零的顶点可以使用栈，也可以使用队列III，若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为1
A．I、III
B．II、ⅡI
C．II
D．In
请帮忙给出正确答案和分析，谢谢！
-
正确答案：DI中，对于一个存在环路的有向图，使用拓扑排序算法运行后，肯定会出现有环的子图，在此环中就无法再找到入度为0的结点了，拓扑排序也就进行不下去了。II中，注意，如果两个结点之间不存在祖先或子孙关系的话，则它们在拓扑序列中的关系是任意的(即前后关系任意)，从而使用栈和队列都可以，因为进栈或队列的都是入度为0的结点，此时入度为0的所有结点是没有关系的。ⅡI中，可假设两个孤立的顶点，虽满足题设要求，但拓扑排序不唯一。