对于一个有向图，不用拓扑排序，如何判定图中是否存在环？

题目

如果没有搜索结果或未解决您的问题，请直接联系老师获取答案。

相似问题和答案

第1题：

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

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

参考答案：错误

第2题：

拓扑排序算法仅适用于有向无环图。()

参考答案：错误

第3题：

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

A、求关键路径的方法

B、求最短路径的Dijkstra方法

C、宽度优先遍历算法

D、深度优先遍历算法

参考答案：D

第4题：

拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图中的有向图， ( ) 不是其的一个拓扑序列。

A.1526374
B.1526734
C.5123764
D.5126374

答案：C

解析：

拓扑序列是将有向图中所有顶点排成一个线性序列，并且该序列满足：若在图中存在从顶点Vi到Vj的路径，则在该线性序列中，顶点i必然在顶点Vj之前。对有向图进行拓扑排序的方法如下：① 在有向图中选择一个入度为零(没有前驱)的顶点且输出之：② 从有向图中删除该顶点及从该顶点出发的所有弧；③ 重复上述两步，直至图中不存在入度为0的顶点为止。对于图3-4所示的有向图，进行拓扑排序的顶点序列有：5126374、5126734、1526374和1526734。而选项C的"5123764"不是其中的一个拓扑序列。

第5题：

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

A.41235

B.43125

C.42135

D.41=325

正确答案：A

第6题：

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

A.深度优先遍历

B、拓扑排序

C.求最短路径

D、求关键路径

参考答案：B

第7题：

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

A．求最小生成树

B．求最短路径

C．拓扑排序

D．图的遍历

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

第8题：

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

A.对

B.错

正确答案：A

第9题：

拓扑排序运算只能用于()

A.带权有向图

B.连通无向图

C.有向无环图

D.无向图

正确答案：C

第10题：

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

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

答案：A

解析：

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

对于一个有向图，不用拓扑排序，如何判定图中是否存在环？

题目

相似问题和答案

更多相关问题

相关内容