下面给出的四种操作中,能够检测出一个有向图是否存在回路的是()。

题目

下面给出的四种操作中,能够检测出一个有向图是否存在回路的是()。

  • A、广度优先搜索
  • B、拓扑排序
  • C、求最短路径
  • D、求关键路径
参考答案和解析
正确答案:B
如果没有搜索结果或未解决您的问题,请直接 联系老师 获取答案。
相似问题和答案

第1题:

判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用求最短路径的Dijkstra方法。()

此题为判断题(对,错)。


参考答案:错误

第2题:

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

A.41235

B.43125

C.42135

D.41=325


正确答案:A

第3题:

判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用()。

A、求关键路径的方法

B、求最短路径的Dijkstra方法

C、宽度优先遍历算法

D、深度优先遍历算法


参考答案:D

第4题:

下面()可以判断出一个有向图中是否有环(回路)。

  • A、广度优先遍历
  • B、拓扑排序
  • C、求最短路径
  • D、求关键路径

正确答案:B

第5题:

判断一个有向图是否存在回路的方法除了可以利用拓扑排序方法外。还可以用()。

A.求关键路径的方法
B.求最短路径的Dijkstra方法
C.广度优先遍历算法
D.深入度优先遍历算法

答案:D
解析:
判断一个图是否存在回路的方法包括:(1)设图G是n个顶点的无向图,若G的边数e>=n,则图G中一定有回路存在。(2)设图G是n个顶点的无向连通图,若G的每个顶点的度>=2,则图G中一定有回路存在。(3)利用拓扑排序算法可以判断图中是否存在回路。即在拓扑排序输出结束后所余下的顶点均有前驱,则说明只得到了部分顶点的拓扑有序序列,图中存在有回路。(4)利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说,若深度优先遍历过程中遇到了回边则必定存在环;对于有向图来说,这条回边可能是指向深度优先森林中另一棵生成树上顶点的弧;但是,如果从有向图上的某个项点v出发进行深度优先遍历,若在dfs(v)结束之前出现一条认顶点v到顶点v的回边,因u在生成树上是v的孙子,则有向图必定存在半含顶点u和顶点v的环。

第6题:

一个状态转换图是由一组矢线连接的有限个结点所组成的什么()。

A有向图

B无向图

C无回路有向图

D强连通的有向图


正确答案:A

第7题:

判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以用()。

A.广度优先遍历算法
B.深度优先遍历算法
C.求关键路径的方法
D.求最短路径的方法

答案:B
解析:
当有向图中无回路时,从某顶点出发进行深度优先遍历时,出栈的顺序(退出DFSTraverse算法)即为逆向的拓扑序列。

第8题:

判断有向图是否存在回路,利用()方法最佳。

A.求关键路径

B.求最短路径

C.拓扑排序

D.广度优先遍历


正确答案:C

第9题:

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

A.41235
B.43125
C.42135
D.41325

答案:A
解析:
拓扑排序通俗一点来讲,其实就是依次遍历没有前驱结点的结点。而某一时刻没有前驱结点的结点有可能存在多个,所以一个图的拓扑排序可能有多个。
4号结点没有前戏,所以拓扑排序的第一个元素是4。当4访问完了就可以访问1,1号访问完了就可以访问2,2号访问完了就可以访问3或5。所以拓扑排序结果为:412(35)。


第10题:

下面哪一个方法可以判断出一个有向图中是否有环回路()

  • A、深度优先遍历
  • B、拓扑排序
  • C、求最短路径
  • D、求关键路径

正确答案:A,B

更多相关问题