在有向无环图中,按照拓扑排序得到的顶点序列,满足什么特性?
答案解析
核心考点说明:本题考察有向无环图的拓扑排序特性。拓扑排序是将有向无环图的所有顶点排成线性序列,使得图中任意一对顶点 u 和 v,若存在边 ,则 u 在序列中出现在 v 的前面。
解题思路分析:拓扑排序的定义决定了序列中顶点的前后关系,正确答案需要体现该关系。
选项分析:
A. 任意两个顶点之间的顺序不固定:虽然拓扑排序结果不唯一,但是同一排序的顶点前后顺序有一定约束。
B. 后出现的顶点的所有前驱顶点在序列中在其前面:符合拓扑排序的定义。
C. 先出现的顶点的所有后继顶点在序列中在其前面:与拓扑排序的定义相反。
D. 序列中的顶点按照其出度的大小排列:拓扑排序与出度大小没有直接关系。
易错点提醒:容易混淆拓扑排序中顶点的前后关系,拓扑排序要求依赖关系保持,而非简单的顺序或大小排列。
正确答案:B