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

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

admin2021-01-13  90
问题 拓扑序列是有向无环图中所有顶点的一个线性序列，若有向图中存在弧或存在从顶点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)