作者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