作者peropero1 (嗚嗚~~~~)
看板Grad-ProbAsk
標題[理工][軟體]99台大軟體設計
時間Sat Dec 11 21:23:55 2010
第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
1F：推 tureday:用DFS做，沒迴圈,點會比邊多，有迴圈,用的點邊一樣多.O(V) 12/12 02:14
2F：推 skill91002:請問樓上是用DFS找back edge的找法嗎？ 12/12 09:17
3F：→ peropero1:可以請問一下有迴圈跟沒迴圈的差異嗎??? 12/12 15:58
4F：推 christianSK:沒有迴圈的話 |E|<=|V|-1 O(E) = O(V) 12/12 16:05
5F：→ christianSK:有迴圈的話 O(E) = O(V^2) 在worst case下 12/12 16:05
6F：→ christianSK:我也想知道一樓 怎麼在有迴圈下可以用O(V) 完成 12/12 16:06
7F：→ christianSK:我剛剛說的好像是要連通才是@@ 12/12 16:07
8F：→ peropero1:話說…題目只說是undirect…並沒有說是簡單圖或多重圖 12/12 16:41
9F：→ peropero1:所以我想worst cast應該不只O(V^2) ??? 12/12 16:41
※ 編輯: peropero1 來自: 59.126.0.166 (12/12 16:42)
10F：→ peropero1:畢竟Kn似乎看來不是worst case... 12/12 16:43
11F：推 tureday:只要判斷有迴圈就OUTPUT有迴圈,Kn也不用所有迴圈都找過 12/13 18:25
12F：推 tureday:所以有迴圈的話,所搜尋過的點和邊會一樣 12/13 18:27
13F：→ tureday:設一個v的前行點u,w是由v出發連到的點,DFS做到前方沒有沒 12/13 18:52
14F：→ tureday:找過的點就會backtracking,這時候如果有w=/=u就有迴圈 12/13 18:55