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