下列关于拓扑排序的说法中，错误的是（ ）。

Ⅰ．若某有向图存在环路，则该有向图一定不存在拓扑排序 Ⅱ．在拓扑排序算法中，为暂存入度为零的顶点，可以使用栈，也可以使用队列 Ⅲ．若有向图的拓扑有序序列唯一，则图中每个顶点的入度和出度最多为 1 Ⅳ．若有向图的拓扑有序序列唯一，则图中入度为 0 和出度为 0 的顶点都仅有 1 个

A. Ⅰ、Ⅲ、Ⅳ B. Ⅲ、Ⅳ C. Ⅱ、Ⅳ D. Ⅲ

[tag_link]

正确答案：D

结论

D 正确。

推导

陈述Ⅰ正确：有向环不能拓扑排序。陈述Ⅱ正确：栈或队列均可暂存入度为零的顶点。陈述Ⅲ错误：a→b、a→c、b→c 的 DAG 唯一序列 a,b,c，但 c 入度为 2。陈述Ⅳ正确：多个入度零或出度零顶点可交换。组合选项中，A 包含Ⅰ、Ⅲ、Ⅳ，B 包含Ⅲ、Ⅳ，C 包含Ⅱ、Ⅳ，只有选项 D 仅包含Ⅲ这一错误陈述。

易错点

唯一序列不等于每个顶点度数至多 1，关键是每一步是否只有一个可选入度零顶点。