🏷️ 知识点：边约束验证

已知有向图 G=(V,E)，其中 V={v₁,v₂,v₃,v₄,v₅,v₆,v₇}，E={⟨v₁,v₂⟩,⟨v₁,v₃⟩,⟨v₁,v₄⟩,⟨v₂,v₅⟩,⟨v₃,v₅⟩,⟨v₃,v₆⟩,⟨v₅,v₇⟩,⟨v₆,v₇⟩,⟨v₄,v₆⟩}，G 的拓扑序列是（ ）。

A. {v₁,v₃,v₄,v₆,v₂,v₅,v₇} B. {v₁,v₃,v₂,v₆,v₄,v₅,v₇} C. {v₁,v₃,v₄,v₅,v₂,v₆,v₇} D. {v₁,v₂,v₅,v₃,v₄,v₆,v₇}

正确答案：A

结论

A 满足所有有向边的起点先于终点，是合法拓扑序列。

推导

逐项验证边约束：v₁ 在 v₂、v₃、v₄ 之前；v₂、v₃ 在 v₅之前；v₃、v₄ 在 v₆之前；v₅、v₆ 在 v₇之前。A 的位置顺序全部满足这些约束。

易错点

A 正确；B 将 v₆ 放在 v₄ 前违反 v₄→v₆；C 将 v₅ 放在 v₂ 前违反 v₂→v₅；D 将 v₅ 放在 v₃ 前违反 v₃→v₅。