作者ledia (下班後才下棋)
站内Prob_Solve
标题Re: [问题] 侦测cycle的演算法
时间Mon Sep 3 16:17:43 2007
※ 引述《amy10062003 (徘徊在抉择之间)》之铭言：
: 请问一下
: 如果给定一个图形
: G(V,E) V: 节点数 E: edge
: 要如何写出侦测cycle的演算法呢?
: 同时run time 必须是 O(V) 跟 E 无相关
: 谢谢
: ps: 我有查到 Floyd's cycle finding algorithm 但感觉似乎要O(V+E) ...
Floyd's cycle finding algorithm 是检查 sequence 有没有循环用的
应该不是你要的
general graph 的 cycle detection
应该只要 DFS 看有没有 back edge 就可以了
DFS 的确是 O(|V|)
--
有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。
存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你
，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也
是比较不容易被击倒的人。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.56
1F：推 amy10062003:我刚刚有找过..但是DFS他资料写O(V+E)所以我才找别的 09/03 16:48
2F：推 a127a127:重点是有向图还是无向图 如果是无向图的话 DFS过程中只要 09/04 16:03
3F：→ a127a127:有连到以前走过的点就表示有圈 前向後向横跨边都不能有 09/04 16:04
4F：→ a127a127:所以时间复杂度为O(|V|) 09/04 16:07
5F：推 amy10062003:所以如果single source就能直接用DFS? 09/04 21:09
6F：推 a127a127:只要每个点都恰好被访问过一次就可以了 大於1就是有圈 09/04 22:44
7F：→ a127a127:更正一下 DFS不会有横跨边 又因为无向图 所以没有分前後 09/04 22:47
8F：→ a127a127:总之 就是只要有点要被访问第2次就可以跳开了 因为有圈 09/04 22:48
9F：→ a127a127:有圈之下 最多也只需要V的时间 没有圈E<V 也是O(V) 09/04 22:50
10F：→ a127a127:再更正—_—" 因为无向图所以才不会有横跨边... 09/04 22:51
11F：推 ledia:与 single source 无关, 只要无向图且连通 哪个点开始都一样 09/05 21:13
12F：→ ledia:至於 O(|V|) 就如 a127a127 所解释的 09/05 21:13