[理工] 交大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资演两题