我要招人

去企业版

首页 > 试题广场 >

以下哪些算法可以检测一个有向图中是否存在环（）

[不定项选择题]

```
深度优先遍历
```
```
广度优先遍历
```
```
拓扑排序
```
```
关键路径算法
```

查看正确选项

我的天鸭

简单说一下算法步骤，为什么选DFS和拓扑排序：

DFS的时候，如果要访问的元素已经访问过，它在当前的栈内还没出栈，那么就是有环。BFS不行是因为可能有多个节点指向该节点，不一定是因为有环。

拓扑排序会循环执行以下两步：
(1) 选择一个入度为0的顶点，输出
(2) 从图中删除此顶点以及所有的出边
循环结束后，若输出的顶点数小于网中的顶点数，则说明有回路

发表于 2019-08-04 17:26:09 回复(0)

风木青

关键路径算法要求图内无环，这是算法的起始条件，但算法本身不含有判断是否有环的部分。

发表于 2019-11-30 14:45:02 回复(0)

上岸er

这是一道著名的烂题，AC和ACD的版本都有。求关键路径第一步就是拓扑排序，但它本身和检测环路没关系。所以我该怎么办？我只能祈祷考试别考种模棱两可的题，没有意义

发表于 2022-08-11 09:42:33 回复(0)

圣光·明流火

拓扑排序。。想都不用想这玩意的存在就是为了检查有无环。。

深度优先遍历。。尽可能深的搜索树的分支。。查着查着肯定有环的存在。。

发表于 2019-05-14 15:46:55 回复(0)

simon_free

关键路径算法主要用于确定项目计划中的关键路径和最短时间，并不能直接用于检测有向图中的环路。有向图中的环路检测通常使用广度优先搜索或深度优先搜索算法实现。

发表于 2023-11-23 17:22:27 回复(0)

辉小歌

这题王道上做过，233页第6题。书上答案 ACD。这里AC。不严谨的题。。

发表于 2022-08-21 14:54:15 回复(1)

云海翻腾

广度优先遍历不行

发表于 2022-07-30 16:19:37 回复(0)

秋越海

无向图，若深度优先遍历过程中遇到回边(即指向已访问过的顶点的边），则该无向图必定存在环路。
参考图的关节点与重连通分量，图的深度优先生成树。

使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：
求出图中所有结点的度。
将所有度 <= 1 的结点入队。（独立结点的度为 0）
当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。
如果相邻节点的度变为一，则将相邻结点入队。
循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；
反之，则有环
////////////////////////////////////////////////////////////////////////
有向图判断是否存在环
对于有向图，利用拓扑排序来判断是否存在环：
对于无环的有向图，对其进行拓扑排序可输出其所有顶点，而有环的图则不行！
////////////////////////////////////////////////////////////////////////
使用拓扑排序判断无向图和有向图中是否存在环的区别在于：
在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；
在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队
////////////////////////////////////////////////////////////////////////
关键路径虽然不允许有环 
在求关键路径时如果得到的拓朴有序序列中顶点的个数小于网中顶点个数n，则说明网中有环，
不能求出关键路径，算法结束。
且是在无向图中才有解。
求解关键路径问题,必须是有向无环图才有关键路径。

发表于 2022-05-25 21:27:49 回复(0)

学术废物

连续做到两个含环的题目关键路径和最短路径在我认为也是可以选的虽然两道题都没选😓

发表于 2022-03-16 21:57:32 回复(0)

空中转体一周半

**答案 d可以判断是否存在回路

发表于 2020-09-22 15:55:42 回复(3)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师哔哩哔哩测试工程师图 PHP工程师 2019 Java工程师

来自：哔哩哔哩2019秋招技...

上传者：小小

难度：

10条回答 266收藏 7677浏览

以下哪些算法可以检测一个有向图中是否存在环（）

问题信息

热门推荐

相关试题

以下哪些算法可以检测一个有向图中是否存在环（ ）

问题信息

热门推荐

相关试题

以下哪些算法可以检测一个有向图中是否存在环（）