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

[newpuma (還很新)]

如題 在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個邊
在樹上應該是這樣無誤，因為邊數一定是點數-1
※ 編輯: newpuma (42.72.162.23), 02/02/2017 18:58:09
→ gouya: Kn的邊數就是C(n,2) 題目應該不會要你去偵測Tree有無cycle
推 yorunohoshi: 假設是在任意圖上用DFS做，tree edge最多n-1個，再
→ yorunohoshi: 來就是back edge了，只要偵測到back edge就有cycle
→ yupog2003: connected graph超過n-1個edge就有cycle了？
→ yupog2003: 偵測到back edge就直接return有cycle下面都不用做
推 yorunohoshi: 話說你最後的問題應該是中央考的?中央寫O(n)但立宇
→ yorunohoshi: 的講義把它題目改成O(n+m)，跑BFS可解
→ yorunohoshi: 所以我也好奇怎麼O(n)解QQ
乾 原來是這樣 我也想半天...
→ joeboy: 切點刪除不就不連通了？找到cycle刪除其中一個點吧？
連通圖本身不會有cycle八
推 Astar5566: 找關節點啊 如果找不到就是了
推 boy00114:  http://i.imgur.com/BD0DjFq.jpg 好像沒解法
→ Transfat: 找articulation point也要O(|V|+|E|)吧
萬物基於DFS 囧
※ 編輯: newpuma (42.72.162.23), 02/02/2017 23:04:06
推 aa06697: 為什麼連通圖不會有cycle啊@@
推 cjoek: spanning tree本身也是一種連通圖
→ aa06697: 樓上在回答我嗎@@ 這樣子也是因為tree所以acyclic 而不是
→ aa06697: 因為connected而acyclic@@
推 AllenPaul: 有沒有cycle應該是看有沒有back edge吧