Re: [問題] 偵測cycle的演算法
看板Prob_Solve (計算數學 Problem Solving)作者ledia (下班後才下棋)時間17年前 (2007/09/03 16:17)推噓5(5推 0噓 7→)留言12則, 3人參與討論串2/2 (看更多)
※ 引述《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
推
09/03 16:48, , 1F
09/03 16:48, 1F
推
09/04 16:03, , 2F
09/04 16:03, 2F
→
09/04 16:04, , 3F
09/04 16:04, 3F
→
09/04 16:07, , 4F
09/04 16:07, 4F
推
09/04 21:09, , 5F
09/04 21:09, 5F
推
09/04 22:44, , 6F
09/04 22:44, 6F
→
09/04 22:47, , 7F
09/04 22:47, 7F
→
09/04 22:48, , 8F
09/04 22:48, 8F
→
09/04 22:50, , 9F
09/04 22:50, 9F
→
09/04 22:51, , 10F
09/04 22:51, 10F
推
09/05 21:13, , 11F
09/05 21:13, 11F
→
09/05 21:13, , 12F
09/05 21:13, 12F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
