2. 考研
  3. 以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ．深度优先遍历 Ⅱ．求最短路径 Ⅲ．拓扑排序 Ⅳ．求关键路径

以下哪些方法可以判断出一个有向图是否有环( )。 Ⅰ．深度优先遍历 Ⅱ．求最短路径 Ⅲ．拓扑排序 Ⅳ．求关键路径

admin2019-05-10  73
问题 以下哪些方法可以判断出一个有向图是否有环(    )。
    Ⅰ．深度优先遍历    Ⅱ．求最短路径    Ⅲ．拓扑排序    Ⅳ．求关键路径
选项 A、仅Ⅰ、Ⅲ
B、仅Ⅰ、Ⅲ、Ⅳ
C、仅Ⅰ、Ⅱ、Ⅲ
D、Ⅰ、Ⅱ、Ⅲ和Ⅳ
答案A
解析 有两种方法可以判断有向图中是否有回路。用深度优先遍历的方法，如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点j～v的边，由于j在生成树上是v的子孙，则图中必定存在包含v和j的环，因此Ⅰ可以；用拓扑排序的方法，在拓扑排序过程中，每次要删去一个没有前驱的顶点，如果最后图中所有顶点都被删除，则表示没有环，否则有环，因此Ⅲ正确。而最短路径和关键路径(建立在无环的AOE网的基础之上)都是不可以判断的。
    补充：还有一个出题点是间接出题，即若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图一定有什么?想必90％以上的考生都会选择有环，但是没有环这个选项，只有顶点数目大于l的强连通分量这个选项，此时考生必须知道顶点数目大于1的强连通分量就表明有环。
转载请注明原文地址:https://www.kaotiyun.com/show/I9Ci777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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