[理工] 交大 109 資演 2題

看板Grad-ProbAsk作者booowei1203 (wei)時間3年前 (2020/12/16 20:27)推噓3(3推 0噓 7→)

留言10則, 3人參與討論串1/1

想問一下交大 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://www.ptt.cc/bbs/Grad-ProbAsk/M.1550485751.A.557.html）可是我遇到今年這題又不會了，不知道大家是怎麼想出這種題目的解法的qq https://imgur.com/h2aYLzp

https://imgur.com/SFtMyzR

附個答案網址：https://pse.is/3amxvj 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.153.215 (臺灣) ※ 文章網址: https://www.ptt.cc/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

推

stu199712

12/16 20:37, 3年前 , 1^F

12/16 20:37, 1^F

→

stu199712

12/16 20:37, 3年前 , 2^F

12/16 20:37, 2^F

→

stu199712

12/16 20:38, 3年前 , 3^F

12/16 20:38, 3^F