[理工] [資結]-DFS

[gn00618777 (123)]

The complexity for performing depth first search and breath first search on
a n-vertex undirected graph which is represented by an adjacency list is
O(n)

洪X解答說是false 所以答案為O(e+v)，但是偉X說是O(n^2)，網路上找說用list是O(2|v|)
那到底是哪一個＝ ＝?因為洪X的解答網路上的評價...所以每錯一題我就想問一下

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.138.105.159
→ stdio:o+e
→ stdio:更正 e+v
推 polomoss:用adjacency list O(v+e) , matrix O(v^2)
→ stdio:2v也對...
→ gn00618777:嗯 了解了
→ crazyjoe:跟三樓的一樣
→ gn00618777:那既然2v也對為何他說O(N)不行..
→ gn00618777:O(2|v|)就是O(2n)=O(n)阿＝ ＝ 可是解答說不對
→ gn00618777:仔細看了一下我好像打錯了..應該是O(e)
→ gn00618777:考慮link list數 2e -->O(e)不是O(n)
推 luckysky1:e夠大就變成n^2了？
推 FRAXIS:樓上說的沒錯  但是一般圖論的演算法都是把e和v分開