单选题 以下有关拓扑排序的说法中,错误的是______。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
  • A.仅Ⅰ、Ⅲ
  • B.仅Ⅱ、Ⅲ
  • C.仅Ⅱ
  • D.仅Ⅲ
【正确答案】 D
【答案解析】[解析] Ⅰ:如果一个有向图存在环路,则肯定不会存在拓扑排序,因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。 Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。 Ⅲ:一个反例如图所示。该图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。 [*]