在有向图 G 的拓扑序列中，若顶点 Vᵢ 在顶点 Vⱼ 之前，则下列情形不可能出现的是（ ）。

A. G 中有弧<Vᵢ, Vⱼ> B. G 中有一条从 Vᵢ 到 Vⱼ 的路径 C. G 中没有弧<Vᵢ, Vⱼ> D. G 中有一条从 Vⱼ 到 Vᵢ 的路径

拓扑排序

[tag_link]

正确答案：D

拓扑序列是针对有向无环图（DAG）的一种顶点排序，要求对于图中的任意有向边，起点在终点之前。

因此，若顶点Vᵢ在拓扑序列中位于Vⱼ之前，则图中不能存在从Vⱼ到Vᵢ的路径，否则会形成环路，违反拓扑序列的定义。

分析选项：

• A：存在弧（即从Vᵢ到Vⱼ的有向边）是可能的，因为该边方向与序列顺序一致，符合拓扑序列要求。 >
• B：存在从Vᵢ到Vⱼ的路径也是可能的，路径意味着Vᵢ是Vⱼ的前驱，在拓扑序列中自然位于其前。 >
• C：没有弧同样可能，因为Vᵢ和Vⱼ之间可能通过其他顶点间接连通，或没有直接关联但序列顺序由其他边决定。 >
• D：存在从Vⱼ到Vᵢ的路径是不可能的，因为如果有这样的路径，根据拓扑序列性质，Vⱼ必须位于Vᵢ之前，这与已知的Vᵢ在Vⱼ之前矛盾。 >

因此，不可能出现的情形是D。 >