[理工][軟體]99台大軟體設計

[peropero1 (嗚嗚~~~~)]

第5題
Give a pseudocode that determines whether or not an undirected graph
G=(V,E) contains a cycle. You need to show that your pseudocode runs
in O(V) time. You may assue that the adjacency-list representation
of G is given, and for each vertex u in V, Adj[u] consists of all the
vertices adjacent to u in G.

題目要求演算法需在O(V)內完成
想請問一下版上大大該怎麼做??
(是否可直接用DFS求解??其複雜度為Θ(V+E))

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.126.0.166
推 tureday:用DFS做，沒迴圈,點會比邊多，有迴圈,用的點邊一樣多.O(V)
推 skill91002:請問樓上是用DFS找back edge的找法嗎？
→ peropero1:可以請問一下有迴圈跟沒迴圈的差異嗎???
推 christianSK:沒有迴圈的話 |E|<=|V|-1 O(E) = O(V)
→ christianSK:有迴圈的話 O(E) = O(V^2) 在worst case下
→ christianSK:我也想知道一樓 怎麼在有迴圈下可以用O(V) 完成
→ christianSK:我剛剛說的好像是要連通才是@@
→ peropero1:話說…題目只說是undirect…並沒有說是簡單圖或多重圖
→ peropero1:所以我想worst cast應該不只O(V^2) ???
※ 編輯: peropero1       來自: 59.126.0.166         (12/12 16:42)
→ peropero1:畢竟Kn似乎看來不是worst case...
推 tureday:只要判斷有迴圈就OUTPUT有迴圈,Kn也不用所有迴圈都找過
推 tureday:所以有迴圈的話,所搜尋過的點和邊會一樣
→ tureday:設一個v的前行點u,w是由v出發連到的點,DFS做到前方沒有沒
→ tureday:找過的點就會backtracking,這時候如果有w=/=u就有迴圈
→ sneak: 所以有迴圈的話,所搜尋 https://noxiv.com
→ sneak: //noxiv.com https://daxiv.com
→ sneak: 請問樓上是用DFS找b https://daxiv.com