拓扑序列是有向无环图中所有顶点的一个线性序列,若有向图中存在弧或存在从顶点v到w的路径,则在该有向图的任一拓扑序列中,v一定在w之前。下面有向图的拓扑序列是_________。

admin2021-01-13  32

问题 拓扑序列是有向无环图中所有顶点的一个线性序列,若有向图中存在弧或存在从顶点v到w的路径,则在该有向图的任一拓扑序列中,v一定在w之前。下面有向图的拓扑序列是_________。

选项 A、4 1 2 3 5
B、4 3 1 2 5
C、4 2 1 3 5
D、4 1 3 2 5

答案A

解析 本题考查数据结构基础知识。
对有向无环图网进行拓扑排序的方法如下:
①在AOV网中选择一个入度为零(没有前驱)的顶点v且输出它:
②从网中删除该顶点v以及与该顶点有关的所有边;
③重复上述两步,直至网中不存在入度为零的顶点为止。
按照上述方法,拓扑序列的第一个顶点为4,执行①和②步之后的有向图如下图(a)所示。接下来再输出的顶点只能为1,因此执行①和②步之后的有向图如下图(b)所示。接下来再输出的顶点只能为2,因此①和②步之后的有向图如下图(c)所示。因此,拓扑序列为41235。
转载请注明原文地址:https://kaotiyun.com/show/ytCZ777K
0

相关试题推荐
最新回复(0)