Re: [問題] 偵測cycle的演算法

[ledia (下班後才下棋)]

※ 引述《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
推 amy10062003:我剛剛有找過..但是DFS他資料寫O(V+E)所以我才找別的
推 a127a127:重點是有向圖還是無向圖 如果是無向圖的話 DFS過程中只要
→ a127a127:有連到以前走過的點就表示有圈 前向後向橫跨邊都不能有
→ a127a127:所以時間複雜度為O(|V|)
推 amy10062003:所以如果single source就能直接用DFS?
推 a127a127:只要每個點都恰好被訪問過一次就可以了 大於1就是有圈
→ a127a127:更正一下 DFS不會有橫跨邊 又因為無向圖 所以沒有分前後
→ a127a127:總之 就是只要有點要被訪問第2次就可以跳開了 因為有圈
→ a127a127:有圈之下  最多也只需要V的時間   沒有圈E<V 也是O(V)
→ a127a127:再更正—_—"   因為無向圖所以才不會有橫跨邊...
推 ledia:與 single source 無關, 只要無向圖且連通 哪個點開始都一樣
→ ledia:至於 O(|V|) 就如 a127a127 所解釋的