為什麼這篇BFS DFS鄉民發文收入到精華區：因為在BFS DFS這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者newpuma (還很新)看板Grad-ProbAsk標題[理工] 可以說DFS、BFS是O(n...
如題 在adjacency list中DFS、BFS的時間複雜度都是O(|V|+|E|)
剛好今天寫中央遇到幾題偵測是否cycle，且規定必須在O(n)時間，感覺都是用DFS
但是在圖上E有可能是V(V-1)/2嗎，這樣我可以說我使用的DFS成長速率是O(n)嗎@@
如果在樹上應該肯定是O(n)那在圖上呢？
順便藉題一問有沒有O(n)的時間可以找出連通圖上某一點刪去後仍是連通？(只想的到找
切點...)
求解，謝謝大家
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.162.23
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1486031932.A.1AE.html
※ 編輯: newpuma (42.72.162.23), 02/02/2017 18:45:34
→ gouya: 偵測cycle只要跑V-1個邊02/02 18:46
在樹上應該是這樣無誤，因為邊數一定是點數-1※ 編輯: newpuma (42.72.162.23), 02/02/2017 18:58:09
→ gouya: Kn的邊數就是C(n,2) 題目應該不會要你去偵測Tree有無cycle02/02 19:13
推 yorunohoshi: 假設是在任意圖上用DFS做，tree edge最多n-1個，再02/02 19:19
→ yorunohoshi: 來就是back edge了，只要偵測到back edge就有cycle02/02 19:19
→ yupog2003: connected graph超過n-1個edge就有cycle了？02/02 19:22
→ yupog2003: 偵測到back edge就直接return有cycle下面都不用做 02/02 19:23
推 yorunohoshi: 話說你最後的問題應該是中央考的?中央寫O(n)但立宇02/02 19:26
→ yorunohoshi: 的講義把它題目改成O(n+m)，跑BFS可解 02/02 19:26
→ yorunohoshi: 所以我也好奇怎麼O(n)解QQ02/02 19:26
乾 原來是這樣 我也想半天...→ joeboy: 切點刪除不就不連通了？找到cycle刪除其中一個點吧？02/02 19:28
連通圖本身不會有cycle八推 Astar5566: 找關節點啊 如果找不到就是了02/02 19:55
→ Transfat: 找articulation point也要O(|V|+|E|)吧02/02 21:13
萬物基於DFS 囧※ 編輯: newpuma (42.72.162.23), 02/02/2017 23:04:06
推 aa06697: 為什麼連通圖不會有cycle啊@@ 02/03 11:13
推 cjoek: spanning tree本身也是一種連通圖 02/03 12:52
→ aa06697: 樓上在回答我嗎@@ 這樣子也是因為tree所以acyclic 而不是 02/03 15:49
→ aa06697: 因為connected而acyclic@@ 02/03 15:49
推 AllenPaul: 有沒有cycle應該是看有沒有back edge吧 02/03 23:53