有一个有向图,包含节点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