作者booowei1203 (wei)
看板Grad-ProbAsk
标题[理工] 交大 109 资演 2题
时间Wed Dec 16 20:27:21 2020
想问一下交大 109 资演的两题
第一题是判断一个具有 n 个 node 的图是否为 2-colorable 的演算法的时间复杂度
https://imgur.com/17RaKhB
答案是 (B) O(n^2)，但我选 (A) O(n)
原因是因为我觉得只要 traverse 一遍图上的每一个点，
就可以判断是否为 2-colorable 了
後来查了一下发现这个网站（
https://pse.is/38yh5r）
说可以用 BFS 判断是否为 2-colorable
时间复杂度为 O(V+E)
所以我觉得好奇怪，是我哪里理解错了吗？还是答案错了？
https://imgur.com/89Kkx4y
-----
第二个想问的问题是
用 Hamilonian cycle 判断一个图，是否具有起点、终点为特定点的 Hamilonian Path
这题类似的题目交大已经连续出了三年了
之前看过 F大解出 107年的类似题
（在这里：
https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1548560644.A.EB0.html）
可是我遇到今年这题又不会了，不知道大家是怎麽想出这种题目的解法的qq
https://imgur.com/h2aYLzp
https://imgur.com/SFtMyzR
附个答案网址：
https://pse.is/3amxvj
谢谢！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.73.153.215 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1608121647.A.177.html
※ 编辑: booowei1203 (42.73.153.215 台湾), 12/16/2020 20:34:48
※ 编辑: booowei1203 (42.73.153.215 台湾), 12/16/2020 20:37:25
1F：推 stu199712: 我想第一题的BFS应该是用adjacency matrix 12/16 20:37
2F：→ stu199712: 因为选项里都没有跟edge有关 12/16 20:37
3F：→ stu199712: 用adjacency list才会是你说的O(V+E) 12/16 20:38
4F：→ stu199712: adjacency matrix的话就是O(V^2) 12/16 20:39
5F：→ booowei1203: 哦哦哦！我懂了 感谢！ 12/16 20:43
6F：→ booowei1203: 那如果用 adjacency list 的话，是不是可以这样想 12/16 20:45
7F：→ booowei1203: 因为一个图最多有 V*(V-1)/2 个 edge 12/16 20:46
8F：→ booowei1203: 所以O(V+E)=O(V^2)，所以用adjacency list还是O(V^2) 12/16 20:48
9F：推 stu199712: 虽然这样看不直观但推导没错 12/16 20:57
10F：推 alex391a: V+E对V来说是V^2 12/17 15:45
11F：→ oscar90702: 想请问交大的考古题去哪里下载？感谢。 12/21 18:52
※ 编辑: booowei1203 (223.137.76.141 台湾), 01/21/2021 22:13:38