有一个有向图,包含节点A, B, C, D, 其中有以下边:A->B, A->C, B->D。 那么,以下哪个节点序列不是该图的有效拓扑排序?

答案解析

核心考点说明:本题考查有向无环图的拓扑排序。拓扑排序要求对于有向图中的任意一条边 (u, v),节点u必须出现在节点v之前。 解题思路分析:根据给定的边的关系,A必须在B和C之前,B必须在D之前。我们检查每个选项是否满足这些条件。 选项分析: A. A, B, C, D 满足A->B 和 A->C 和 B->D 的顺序。 B. A, C, B, D 满足 A->C 和 A->B,但是 满足 B->D的顺序。 C. A, B, D, C 不满足, 因为C可以在D前面。 D. C, A, B, D 不满足,因为A必须在B之前,且A必须在C前面。 易错点提醒:拓扑排序可能存在多种结果,但所有结果都必须保证有向边从前指向后。 正确答案的关键依据: 选项D不满足A必须在B和C前面。
正确答案:D
随机推荐
开始刷题