作者ahahahahah (Kaneshiro Takeshi)
看板Grad-ProbAsk
標題[理工] 交大105資演 兩題
時間Wed Jan 3 23:42:11 2018
第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
感謝～
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.105.145
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1514994133.A.EAB.html
1F：推 howard31622: bfs跟dfs一樣快 01/03 23:48
2F：→ howard31622: 你那個圖最後畫錯了 01/03 23:48
3F：→ howard31622: 20要在左邊 01/03 23:48
4F：→ ahahahahah: 啊啊發現了QQ 01/03 23:53
5F：推 NCTUFAIWEN: SCC跟這個完全無關 這題是找祖先 共同祖先的不一定是 01/04 07:08
6F：→ NCTUFAIWEN: 可以互通 01/04 07:08
7F：→ ahahahahah: 感謝～請問只有dfs可以追蹤非連通，bfs無法對嗎？ 01/04 10:47
8F：→ howard31622: 兩個一樣快都能找 01/04 11:42
9F：推 andy6666: 這題20在左邊跟右邊是不是都沒答案啊 01/04 13:01
10F：推 sarsman: 照著題目的要求畫就有答案 01/04 14:05
11F：推 Xunion: 大的擺右小的擺左就出來了 01/04 15:52
12F：推 NCTUFAIWEN: SCC的證明是用DFS的性質證的 至於BFS可不可以我倒沒想 01/04 18:31
13F：→ NCTUFAIWEN: 過 不過估計是不行 01/04 18:31