以下有关拓扑排序的说法中,错误的是( )。 Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序 Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列 Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1

admin2014-04-17  35

问题 以下有关拓扑排序的说法中,错误的是(    )。
Ⅰ.如果某有向图存在环路,则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中,既可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1

选项 A、仅Ⅰ、Ⅲ
B、仅Ⅱ、Ⅲ
C、仅Ⅱ
D、仅Ⅲ

答案D

解析 Ⅰ:如果一个有向图存在环路,则该有向图肯定不会存在拓扑排序,这是因为该环路找不到入度为0的结点,拓扑排序自然也就进行不下去了,故Ⅰ正确。
    Ⅱ:使用栈来表示拓扑排序的序列,最后的出栈序列是逆拓扑排序,只需逆转过来即可,只是效率比较低;使用队列时,出队序列就是拓扑排序序列,故使用栈和队列都是可以的,只是效率不等而已,故Ⅱ正确。
    Ⅲ:一个反例如图8—9所示。该有向图的拓扑有序序列是唯一的,但各个顶点的入度和出度可以超出1,故Ⅲ错误。
转载请注明原文地址:https://kaotiyun.com/show/oixi777K
0

最新回复(0)