一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1601|回复: 15
收起左侧

[算法题] 检测图中是否有cycle

[复制链接] |试试Instant~ |关注本帖
JamesJi 发表于 2015-12-13 11:25:52 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
检测graph中是否有cycle,有没有同学指导一下思路和方法?
图分为有向图和无向图两种情况然后图中边的情况可以是由邻接矩阵给出的
lcl3356897 发表于 2015-12-13 11:45:33 | 显示全部楼层
用Set记录访问过的节点,DFS或者BFS走一遍


并查集
回复 支持 反对

使用道具 举报

yls0327 发表于 2015-12-13 12:28:50 | 显示全部楼层
无向图经典做法是两个index一个一次走一步一个一次走两步如果相遇就有cycle
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-13 23:08:52 | 显示全部楼层
yls0327 发表于 2015-12-12 23:28
无向图经典做法是两个index一个一次走一步一个一次走两步如果相遇就有cycle

我好像记得lc里面有一个类似的
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-13 23:37:15 | 显示全部楼层
有向图的话直接上拓扑排序,拓扑排序的最后做完时候就能判断是不是有环了。
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-13 23:41:56 | 显示全部楼层
yucheyang2 发表于 2015-12-13 10:37
有向图的话直接上拓扑排序,拓扑排序的最后做完时候就能判断是不是有环了。

能不能给一个具体的例子?
还有就是如果无向图的时候应该怎么做呢?我现在想到的是用一个标记数组,如果发现这个点已经被标记过,那么说明有环的存在,然后方法应该是这样,可是我怎么来表示一个点的相邻的点或者说怎么表示边呢?
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-13 23:42:24 | 显示全部楼层
lcl3356897 发表于 2015-12-12 22:45
用Set记录访问过的节点,DFS或者BFS走一遍

这个是无向图的情况吧?
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-13 23:56:30 | 显示全部楼层
lcl3356897 发表于 2015-12-12 22:45
用Set记录访问过的节点,DFS或者BFS走一遍

你好,我写了一个··不知道对不对··
https://gist.github.com/JamesJi9277/874eb933028d3a557f9b
回复 支持 反对

使用道具 举报

ryb 发表于 2015-12-14 00:12:21 | 显示全部楼层
无向图中假设n个点 超过n-1条边就一定有环
回复 支持 反对

使用道具 举报

with_god 发表于 2015-12-14 01:14:13 | 显示全部楼层
http://www.cnblogs.com/tenosdoit/p/3644225.html 这个blog里解释的比较详细。
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-14 01:15:27 | 显示全部楼层
with_god 发表于 2015-12-13 12:14
http://www.cnblogs.com/tenosdoit/p/3644225.html 这个blog里解释的比较详细。

非常感谢
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-14 03:03:46 | 显示全部楼层
本帖最后由 JamesJi 于 2015-12-13 14:08 编辑
yucheyang2 发表于 2015-12-13 10:37
有向图的话直接上拓扑排序,拓扑排序的最后做完时候就能判断是不是有环了。

刚刚研究了一下拓扑排序,貌似如果是有向图有环的话,每一个点都是有入度的吧?然而拓扑排序我先要找一个入度为0的点,这样子怎么进行拓扑排序呢

补充一下···就是我还是按照DAG来做,只不过是当我发现某一个点的入度是负数,则代表有cycle,不知道理解的对不对
回复 支持 反对

使用道具 举报

yucheyang2 发表于 2015-12-14 03:37:24 | 显示全部楼层
JamesJi 发表于 2015-12-14 03:03
刚刚研究了一下拓扑排序,貌似如果是有向图有环的话,每一个点都是有入度的吧?然而拓扑排序我先要找一个 ...

你数一下所有点的入度,然后把这些存放在一个HashMap<Node_Identifier, Integer>里面。然后,标准算法里面删Edge,你就删入度。然后做完之后,如果HashMap还剩下什么,就是有环,否则输出拓扑排序的顺序。
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-14 04:08:08 | 显示全部楼层
yucheyang2 发表于 2015-12-13 14:37
你数一下所有点的入度,然后把这些存放在一个HashMap里面。然后,标准算法里面删Edge,你就删入度。然后 ...

我给你发私信了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-12-15 09:27:36 | 显示全部楼层
JamesJi 发表于 2015-12-14 03:03
刚刚研究了一下拓扑排序,貌似如果是有向图有环的话,每一个点都是有入度的吧?然而拓扑排序我先要找一个 ...

循环的退出条件就是不存在入度为0的点。如果还有入度为0的点,那么就删去这些点;如果没有入度为0的点,则退出循环,此时如果还有未处理的点,说明图中有环,否则图中无环。
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-12-15 09:29:43 | 显示全部楼层
stellari 发表于 2015-12-14 20:27
循环的退出条件就是不存在入度为0的点。如果还有入度为0的点,那么就删去这些点;如果没有入度为0的点, ...

恩恩·对的···你说的是对的嘿嘿
·可以按照拓扑排序的步骤来做,最后将拓扑排序的结果集合元素与原来graph中node数来对比
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表