[理工] 可以說DFS、BFS是O(n)嗎？

看板Grad-ProbAsk作者 (還很新)時間7年前 (2017/02/02 18:38), 7年前編輯推噓7(7推 0噓 11→)
留言18則, 10人參與, 最新討論串1/1
如題 在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
→
02/02 18:46, , 1F
偵測cycle只要跑V-1個邊
02/02 18:46, 1F
在樹上應該是這樣無誤，因為邊數一定是點數-1 ※ 編輯: newpuma (42.72.162.23), 02/02/2017 18:58:09
→
02/02 19:13, , 2F
Kn的邊數就是C(n,2) 題目應該不會要你去偵測Tree有無cycle
02/02 19:13, 2F
推
02/02 19:19, , 3F
假設是在任意圖上用DFS做，tree edge最多n-1個，再
02/02 19:19, 3F
→
02/02 19:19, , 4F
來就是back edge了，只要偵測到back edge就有cycle
02/02 19:19, 4F
→
02/02 19:22, , 5F
connected graph超過n-1個edge就有cycle了？
02/02 19:22, 5F
→
02/02 19:23, , 6F
偵測到back edge就直接return有cycle下面都不用做
02/02 19:23, 6F
推
02/02 19:26, , 7F
話說你最後的問題應該是中央考的?中央寫O(n)但立宇
02/02 19:26, 7F
→
02/02 19:26, , 8F
的講義把它題目改成O(n+m)，跑BFS可解
02/02 19:26, 8F
→
02/02 19:26, , 9F
所以我也好奇怎麼O(n)解QQ
02/02 19:26, 9F
乾 原來是這樣 我也想半天...
→
02/02 19:28, , 10F
切點刪除不就不連通了？找到cycle刪除其中一個點吧？
02/02 19:28, 10F
連通圖本身不會有cycle八
推
02/02 19:55, , 11F
找關節點啊 如果找不到就是了
02/02 19:55, 11F
推
02/02 20:39, , 12F
好像沒解法
02/02 20:39, 12F
→
02/02 21:13, , 13F
找articulation point也要O(|V|+|E|)吧
02/02 21:13, 13F
萬物基於DFS 囧 ※ 編輯: newpuma (42.72.162.23), 02/02/2017 23:04:06
推
02/03 11:13, , 14F
為什麼連通圖不會有cycle啊@@
02/03 11:13, 14F
推
02/03 12:52, , 15F
spanning tree本身也是一種連通圖
02/03 12:52, 15F
→
02/03 15:49, , 16F
樓上在回答我嗎@@ 這樣子也是因為tree所以acyclic 而不是
02/03 15:49, 16F
→
02/03 15:49, , 17F
因為connected而acyclic@@
02/03 15:49, 17F
推
02/03 23:53, , 18F
有沒有cycle應該是看有沒有back edge吧
02/03 23:53, 18F
‣ 更多 newpuma 的文章
文章代碼(AID): #1Oammy6k (Grad-ProbAsk)