看板 [ Prob_Solve ]
討論串[問題] 偵測cycle的演算法
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 偵測cycle的演算法
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者amy10062003 (徘徊在抉擇之間)時間17年前 (2007/09/03 16:07), 編輯資訊
1
0
0
內容預覽:
請問一下. 如果給定一個圖形. G(V,E) V: 節點數 E: edge. 要如何寫出偵測cycle的演算法呢?. 同時run time 必須是 O(V) 跟 E 無相關. 謝謝. ps: 我有查到 Floyd's cycle finding algorithm 但感覺似乎要O(V+E) ....
#2
Re: [問題] 偵測cycle的演算法
推噓5(5推 0噓 7→)留言12則，0人參與, 最新作者ledia (下班後才下棋)時間17年前 (2007/09/03 16:17), 編輯資訊
0
0
0
內容預覽:
Floyd's cycle finding algorithm 是檢查 sequence 有沒有循環用的. 應該不是你要的. general graph 的 cycle detection. 應該只要 DFS 看有沒有 back edge 就可以了. DFS 的確是 O(|V|). --. 有時候，
(還有13個字)
首頁
上一頁
1
下一頁
尾頁