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

[单选题]

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

```
求关键路径的方法
```
```
求最短路径的Dijkstra方法
```
```
深度优先遍历算法
```
```
广度优先遍历算法
```

查看正确选项

xxxxxxxxxxxxxxxa

来来来，借着这个题回顾下以前的知识。

DFS搜索可以通过测试生成树是否有背边来判断是否有环，（那么在代码中如何实现呢？比较有意思的问题）

拓扑排序的，如果有环的话，则没有处理完所有的节点，栈或者队列就已经空了。

Dijkstra算法是贪婪算法，其使用于有向图，不一定连通，因为无向图是特殊的有向图，所以其还适合无向图。环的检测不存在的。

关键路径分析法，就更不靠边了，其为AOE网络的一种分析方法，解决最短工期问题等

发表于 2018-06-21 18:51:31 回复(0)

bug##

仔细想一想，用dfs，沿着路径搜索，如果重复回到了已经搜索过的路径，就说明出现了环

发表于 2018-01-24 16:12:57 回复(0)

天尊墨宇

选C

DFS搜索可以通过测试生成树是否有背边来判断是否有环，（那么在代码中如何实现呢？比较有意思的问题）

拓扑排序的，如果有环的话，则没有处理完所有的节点，栈或者队列就已经空了。

Dijkstra算法是贪婪算法，其使用于有向图，不一定连通，因为无向图是特殊的有向图，所以其还适合无向图。环的检测不存在的。

关键路径分析法，就更不靠边了，其为AOE网络的一种分析方法，解决最短工期问题等

发表于 2020-07-13 19:35:28 回复(0)

道友请留步20180723235728

要分清楚dijkstra算法和krustra算法

发表于 2019-03-25 13:49:22 回复(0)

午夜阳光1

使用dfs搜索的时候，如果要访问的元素在当前的栈内还没出栈，那么就是有环。

对于无向图来说，判断回路的方法相同。

发表于 2018-09-20 16:54:20 回复(1)

侯卿

使用dfs搜索的时候，如果要访问的元素在当前的栈内还没出栈，那么就是有环。

发表于 2018-04-20 14:51:22 回复(0)

SSSuper是纸兔斯基

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

发表于 2017-09-19 16:35:13 回复(0)