2. 计算机
  3. 在一个有向图G的拓扑序列中，顶点vi排列在vj之前，说明图G中(59)。

在一个有向图G的拓扑序列中，顶点vi排列在vj之前，说明图G中(59)。

admin2014-05-07  2
问题 在一个有向图G的拓扑序列中，顶点vi排列在vj之前，说明图G中(59)。
选项 A、一定存在弧＜vi，vj＞
B、一定存在弧
C、可能存在vi到vj的路径，而不可能存在vj到vi的路径
D、可能存在vj到vi的路径，而不可能存在vi到vj的路径
答案C
解析 本题考查数据结构基础知识。对一个有向图G进行拓扑排序的方法如下。
①G中选择一个入度为0(没有前驱)的顶点且输出它；
②从网中删除该顶点及其与该顶点有关的所有弧；
③重复上述两步，直至网中不存在入度为0的顶点为止。
显然，若存在弧＜vi，vj＞，则vj的入度就不为0，而要删除该弧，则vi的入度应为0，因此在拓扑序列中，vi必然在vj之前。另外，进行拓扑排序时，可能存在vi和vj的入度同时为0的情形，此时，在第①步可先输出vi，后输出vj因此在拓扑序列中，顶点vi排列在vj之前，不一定存在弧＜vi，vj＞，一定不存在弧＜vi，vj＞，也一定不存在vj到vi的路径，而可能存在vi到vj的路径。
转载请注明原文地址:https://kaotiyun.com/show/FGRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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