违法和不良信息举报 联系客服
免费注册 登录

下列方法中可以判断出一个有向图是否有环（回路）的是（  ）。

题目
单选题
下列方法中可以判断出一个有向图是否有环（回路）的是（  ）。
A

广度优先遍历

B

拓扑排序

C

求最短路径

D

求关键路径

参考答案和解析
正确答案： A
解析：
如果没有搜索结果或未解决您的问题，请直接 联系老师 获取答案。
相似问题和答案

第1题：

采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路)()

A.对

B.错


正确答案：A

第2题：

下面()方法可以判断出一个有向图是否有环。

A.深度优先遍历

B、拓扑排序

C.求最短路径

D、求关键路径


参考答案：B

第3题：

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

A、求关键路径的方法

B、求最短路径的Dijkstra方法

C、宽度优先遍历算法

D、深度优先遍历算法


参考答案：D

第4题：

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

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

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

第5题：

可以判断一个有向图中是否含有回路的方法为()。

A.广度优先遍历

B.深度优先遍历

C.拓扑排序

D.求最短路径


正确答案：C

第6题：

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

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


参考答案：错误

第7题：

判定一个有向图中是否存在回路可以利用(52)方法。

A．求最小生成树

B．求最短路径

C．拓扑排序

D．图的遍历


正确答案：C
解析：拓扑排序方法可以判定一个有向图中是否存在回路，所以答案为C。

第8题：

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

A.求关键路径

B.求最短路径

C.拓扑排序

D.广度优先遍历


正确答案：C

第9题：

判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用______。

A．求关键路径的方法

B．求最短路径的Dijkstra方法

C．深度优先遍历算法

D．广度优先遍历算法


正确答案：C
解析：本题考查AOV的运算，要检测一个工程是否可行，首先就应检查对应的AOV网是否存在回路，检测的一种方法就是对有向图构造其顶点的拓扑有序序列，而对AOV网进行拓扑排序主要考虑顶点的入度，相应的，若在AOV网中考查各项点的出度，这种排序就称为逆排序。同时，还可以利用深度优先遍历进行拓扑排序，因为图中无环，则由图中某点出发进行深度优先遍历时，最先退出DFS函数的顶点即是出度为零的顶点，它是拓扑有序序列中最后的一个顶点。由此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。

第10题：

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

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的环。

更多相关问题
相关内容