1. PTT
  2. Grad-ProbAsk

[理工] 104交大資演！（MST)

作者: Aa841018 (andrew)   2019-12-23 09:57:04
https://i.imgur.com/Jtt4Axj.jpg
請問（b)(c)，（c)我可以理解，但為什麼（b)多了個if就錯了？
然後，詳解我看不是很懂…
作者: gash55025502 (白影弓)   2019-12-23 11:42:00
他們的if P then Q的P跟Q是反過來的b可以簡單舉個反例 如三點兩邊權重都1 此時MST唯一但light edge不唯一c則可以用Prims algorithm去想 在prims回合每個回合都是挑當下cut權重最小的邊 那既然題目說每個cut此種邊都唯一 當然造出來的MST也會唯一
作者: AirComm (AirComm)   2019-12-23 16:47:00
有人可以翻譯一下b選項嗎？light edge 是啥
作者: mistel (Mistel)   2019-12-23 16:49:00
就是橫跨兩個切集權重最小的那個邊
作者: Aa841018 (andrew)   2019-12-23 21:47:00
哦！謝謝各位！
繼續閱讀
[理工] 104台大資工 x86 string問題gash55025502[理工] 97清大資工 計組harryju3[理工] 資演 105交大 （19）（21）ching4562[理工] 離散_機率fmtshk[理工] 105 交大資演數題 3 9 10 19dsa66253[理工] 計組 管線lucy35[理工] 成大計組eric17195[理工] 106北大數學sung100kg[理工] OS process synchronizationAdonisLam[理工] 105交大（BFS)!Aa841018

Links booklink

Contact Us: admin [ a t ] ucptt.com