CSP-J 2023 第一轮 第 12 题：有向无环图的拓扑排序

题目

考虑一个有向无环图，该图包含 $4$ 条有向边：$(1,2),(1,3),(2,4)$ 和 $(3,4)$。以下哪个选项是这个有向无环图的一个有效的拓扑排序?

选项

• A. 4,2,3,1
• B. 1,2,3,4
• C. 1,2,4,3
• D. 2,1,3,4

答案

B

题解

答案是 B：1,2,3,4。

拓扑排序要求：对于每条有向边 \(u\to v\)，\(u\) 必须排在 \(v\) 前面。

根据题目中的边：

• \(1\to2\)、\(1\to3\)：1 必须在 2、3 前面。
• \(2\to4\)、\(3\to4\)：2、3 必须在 4 前面。

因此，1 在最前，4 在最后，2 和 3 的顺序可以互换。有效的拓扑排序有： \[ 1,2,3,4 \quad\text{或}\quad 1,3,2,4 \]

选项中只有 B 符合。