[理工] 交大105資演兩題 ahahahahah PTT批踢踢實業坊

[理工] 交大105資演兩題

作者: ahahahahah (あああああ) 2018-01-03 23:42:11

第25題
https://i.imgur.com/28G0bkC.jpg
那個(b)選項
DFS的演算法不是可以traversal整個圖嗎？
就算沒有連通？
那這樣不會比BFS好嗎？
這題跟林立宇老師教的找strongly connected component 有沒有關係啊？因為老師講義
是用DFS......
另外問一下這題簡單的Huffman
https://i.imgur.com/JTGu5yQ.jpg
畫了3次都一樣==
有沒有人可以幫我看看我哪裡畫錯了？
https://i.imgur.com/raGx86Y.jpg
感謝～

作者: howard31622 (howard) 2018-01-03 23:48:00

bfs跟dfs一樣快你那個圖最後畫錯了20要在左邊

作者: ahahahahah (あああああ) 2018-01-03 23:53:00

啊啊發現了QQ

作者: NCTUFAIWEN (交大廢文王子) 2018-01-04 07:08:00

SCC跟這個完全無關這題是找祖先共同祖先的不一定是可以互通

作者: ahahahahah (あああああ) 2018-01-04 10:47:00

感謝～請問只有dfs可以追蹤非連通，bfs無法對嗎？

作者: howard31622 (howard) 2018-01-04 11:42:00

兩個一樣快都能找

作者: andy6666 (Andy) 2018-01-04 13:01:00

這題20在左邊跟右邊是不是都沒答案啊

作者: sarsman (DeNT15T♠) 2018-01-04 14:05:00

照著題目的要求畫就有答案

作者: Xunion (Xun) 2018-01-04 15:52:00

大的擺右小的擺左就出來了

作者: NCTUFAIWEN (交大廢文王子) 2018-01-04 18:31:00

SCC的證明是用DFS的性質證的至於BFS可不可以我倒沒想過不過估計是不行

繼續閱讀

[理工] 演算法時間複雜度suspect1 [理工] 102 清大資工計科s1020824 [理工] 102 交大機械熱傳kobe874741 [理工] 通訊隨機程序fsociety [理工] 對角化nO25948 [理工] 106清大熱傳導係數chunlin01 [理工] 作業系統hit Ratioooxx5626 [理工] 奇異值分解wsp50317 [理工] 106台大資工離散+線代 2、7、9、10題PunchShadow [理工] 計組kobebset105

[理工] 交大105資演 兩題

[理工] 交大105資演兩題