[理工] 105交大資演(25)

[PTTleader (PTT領導)]

http://imgur.com/a/Pt0pN

想請問這題
BFS DFS 要怎麼做出 equivalence classes
然後
(b)
(c)

各錯在哪裡呢

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.232.14.64
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484724776.A.7B8.html
推 yupog2003: (b)我在想DFS和BFS的time complexity都是O(V+E)，應該
→ yupog2003: 差不多快？
→ yupog2003: BFS可以拿來找connected component，每個connected
→ yupog2003: component就當作是一個disjoint set，一個disjoint
→ yupog2003: set就視為一個equivalence class，阿Union/Find也是可
→ yupog2003: 以拿來找disjoint set，雖然很不嚴謹，但寫的當下想法
→ yupog2003: 是這樣
→ yupog2003: (c)如果union/find用上union by rank和path compressio
→ yupog2003: 應該可以比DFS消耗更少空間
推 Transfat: 我的想法跟樓上一樣，如果用Union-and-find的空間會稍微
→ Transfat: 少一些，就O(n)而已吧
→ yupog2003: 交大資演100分鐘要寫60題，我好多都沒有想得很完整...
推 Transfat: 交大資演寫得完也是很猛QQ
推 weilun911: 寫交大時間都不夠用QQ
推 Transfat: 我想了想又覺得(c)的說法和空間複雜度可能還比較沒關？
→ Transfat: 因為Graph很大，E和V都很多，所以如果用BFS/DFS要O(|V|+
→ Transfat: |E|),如果用Union-by-rank就只要O(log(N)),算是縮小了不
→ Transfat: 少time complexity,所以可能是time complexity的問題
→ Transfat: 晚點再研究看看
→ yupog2003: 當初我也有想到這個問題，但我是想說recursive會用到
→ yupog2003: stack，如果recursive次數越少用的空間也越少，所以也
→ yupog2003: 可以算是跟space complexity有關？
推 Transfat: 有相關，可是題目看不出來recursive次數少不少吧（？）
→ Transfat: 因為他沒給圖，如果是一條長長的graph (像skew-tree)
→ Transfat: 這樣space complexity就會滿低，不過這題純粹只有說一個
→ Transfat: 大Graph
→ yupog2003: 也是沒錯拉...我這樣有點自己腦補了...