题目

对下图进行拓扑排序，可以得到不同拓扑序列的个数是( )。

错因

A

误以为有 4 种排列。a 是唯一入度为 0 的节点，必须排第一，之后只有 b 和 e 的先后可以互换。穷举可得只有 3 种，不是 4 种。

C

少算了一种。穷举时只考虑了 e 排在 b 之前的两种情况，漏掉了 b 排在 e 之前同时 c 插在 e 之前的情况。

D

认为拓扑序列唯一，通常是误以为每一步只有一个候选节点。实际上 a 之后，b 和 e 同时入度降为 0，存在选择分支。

总解析

拓扑排序规则：每次取一个入度为 0 的节点输出，删除它和它的所有出边，重复直到空。

第 1 步：a 是唯一入度为 0 的节点，必须排第一。取走 a 后，b 和 e 的入度都降为 0：

第 2 步：剩下的图里 b 和 e 都可选，这就是分支点。从 b 或 e 任选一条线索往下推：

• 选 b：取走 b，c 入度变 0；剩下可选
  • 再选 c：取走 c，d 入度从 2→1（消去 c→d）；可选 {e}；接着 e、d → 序列 a, b, c, e, d
  • 再选 e：取走 e，d 入度从 2→1（消去 e→d）；可选 {c}；接着 c、d → 序列 a, b, e, c, d
• 选 e：取走 e，d 入度从 2→1；可选 {b}（c 还要等 b）
  • 接着 b → c → d，没有其他分支 → 序列 a, e, b, c, d

最终的 3 个候选拓扑序列：

a, b, c, e, d
a, b, e, c, d
a, e, b, c, d

为什么只有 3 种？关键约束是 c 必须排在 b 之后（b→c），d 永远在最后（d 入度 2，需要 c 和 e 都先走）。所以 e 在 b/c 中间或两端共 3 个位置。

最终答案是 B（3）。