作者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/cn.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