首页 > 试题广场 >

下面算法中可以判断出一个有向图是否有环的是?

[不定项选择题]
下面算法中可以判断出一个有向图是否有环的是：（） 
  • 求最短路径
  • 深度优先遍历
  • 广度优先遍历
  • 拓扑排序
查看正确选项
添加回答
cloudy_x1头像 cloudy_x1
如果没记错的话 求单源最短路的Bellman-Ford算法是可以判断负环的吧，把所有点权值设为-1，跑B-F算法，可以判断出该图有无环。不对么？
发表于 2016-03-11 09:55:05 回复(2)
aaronyoung头像 aaronyoung
感觉广度优先遍历也可以
发表于 2015-09-11 10:30:46 回复(4)
姚军zzz头像 姚军zzz
最短路径是允许有环的，A绝对不选！



发表于 2016-09-16 20:23:52 回复(0)
codersong头像 codersong
深度优先搜索和拓扑排序就不说了，广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环
发表于 2015-10-08 21:26:31 回复(4)
webary头像 webary
判断 无向图 中是否存在回路（环）的算法描述

如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。

算法：

     第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

     第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。

     如果最后还有未删除顶点，则存在环，否则没有环。


有向图是否有环的判定算法，主要有深度优先和拓扑排序两种方法。
所以答案选 BD
编辑于 2016-08-30 18:25:13 回复(1)
不负时光头像 不负时光 
其实你画个图比划一下就很清楚了。通常处理图结构的时候是转换成树结构，通常也就是按照深度遍历的方式转换，
转换的时候是从起始节点开始，找节点的孩子，找到了就保存下来，然后找孩子的孩子，每次找到之后都保存下来，
这就是深度遍历，如果有向图中存在圈圈，那么就必然会出现这种情况“某个节点的孩子已经存在于你保存的节点里了”，
一旦出现就表示有圈圈。
 广度遍历就不行了，因为有向图与树最大的区别之一是两个图的节点可能会有公共的孩子，所以用广度遍历的方式，即使出现了重复，
也不能证明有圈圈。

发表于 2016-03-22 22:07:06 回复(1)
牛客9224906号头像 牛客9224906号
在有负权的情况下，最短路径可以判断出环的存在
发表于 2017-07-14 15:59:11 回复(0)
dragonaxz头像 dragonaxz
一般来说，最短路径是不行的，像Dijkstra，Floyd，都会把顶点到自己的路径长度设为0的。从这方面来说，最短路径是不行的。如果硬是说可以，那这个最短路径的算法应该是自己DIY或者是DFS和BFS这种，那样的情况下才是可以的。但是呢，最短路径算法一般而言就是指的Dijkstra和Floyd，所以说这题目真是。。。
编辑于 2016-11-28 14:37:36 回复(1)
牛客9592436号头像 牛客9592436号
广度优先遍历应该也可以。
如果从A点开始的广度优先遍历能够遍历到B点，说明存在A到B的路径。
同理，从B点开始的广度优先遍历如果能够遍历到A点，说明存在B到A的路径。
那么AB之间就存在环。
所以需要在每个顶点进行一次广度优先遍历，保存所能到达的顶点，然后判断任意两点间能否互相到达。
就是时间复杂度有点高，不实用。。。。
发表于 2017-08-15 13:09:32 回复(1)
丶Berserker头像 丶Berserker
关于拓扑排序判断是否有环。https://blog.csdn.net/weixin_42001089/article/details/84327306
发表于 2022-01-31 09:55:47 回复(0)
硅谷叶问头像 硅谷叶问
搞笑呢，拓扑排序常见写法之一不就是bfs
发表于 2021-10-07 09:03:17 回复(0)
牛客580050057号头像 牛客580050057号
有向图是否有环的判定算法，主要有深度优先和拓扑排序。
发表于 2021-03-13 08:53:30 回复(0)
天尊墨宇头像 天尊墨宇
选BD
检测办法：①拓扑排序：对给定的AOV-网（有向图的网）构造其顶点的拓扑有序序列，若网中所有的顶点都在它的拓扑有序序列中，则该AOV-网中必定不存在环。
                  ②DFS：对于有向图，在深度优先遍历中，如果某个顶点的一个孩子是它的祖先，就存在回路了。
                       对于无向图，如果有某个点被两次以上访问到，那么就存在回路。
编辑于 2020-08-09 11:05:09 回复(0)
我爱吃米皮头像 我爱吃米皮
有么有想到并查集的。。。。
发表于 2017-08-15 16:49:22 回复(0)
ZhangFinder头像 ZhangFinder
如果路径中有负值，则A可以吧
发表于 2016-10-15 20:39:53 回复(0)
小乌头像 小乌
这道题的答案改了吧，之前选的BD
发表于 2016-09-17 17:54:01 回复(0)
牛客297191号头像 牛客297191号
最短路径是怎么能判断出来是有向图的？
发表于 2016-09-03 21:01:40 回复(0)
牛客224737号头像 牛客224737号
？
发表于 2016-05-29 18:17:35 回复(0)
毋亚男头像 毋亚男
B networkx就采用这种Returns the edges of a cycle found via a directed, depth-first traversal
发表于 2016-03-16 21:48:16 回复(0)
牛客492825号头像 牛客492825号
通过把图的权重做成负数求全部最短路径可行，因为有负环的话会出不来
dfs肯定可行，tarjan算法都能求强连通分量
bfs也行，若1个点超过n次进入队列，那么存在环
top排序不清楚
编辑于 2016-03-16 01:55:58 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 图 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 远景 测试开发工程师 大数据开发工程师 Java工程师
来自：2016CVTE校招在...
难度：
23条回答 36504浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号