作者gash55025502 (白影弓)
看板Grad-ProbAsk
標題[理工] 101交大資演的一段程式碼
時間Sun Dec 1 16:54:36 2019
https://i.imgur.com/7XFT3A2.jpg
https://i.imgur.com/ZwHbfvW.jpg
課本上寫這是Prims algorithm的程式碼
自己也有trace了一下
但對最後一段紅筆畫起來的部分有點問題
最後一段有點像是在已選定的Set當中 選連出去的邊中最小的那個
但for loop這樣寫 不是代表他檢查不到第一個點跟最後一個點了嗎？
這樣的話是不是要改成for i=1 to g->n 比較好呢？
感謝～
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.117.248.1 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1575190478.A.756.html
推 bochengchen: 第一個點是起始點所以不用檢查吧 12/01 20:55
→ bochengchen: 再者當已經選了n-1個點的時候，所有in[i]==true 進去 12/01 20:58
→ bochengchen: 了也不會改變吧! 12/01 20:58
→ gash55025502: 但他的起始點是start 不一定要是1吧？ 12/01 20:58
推 twiddlebug: 想請問while裡面第二個for loop的作用是什麼阿 12/02 11:58
推 mistel: for loop的上面兩行不就先v=1了嗎 12/02 12:52
推 mistel: for loop的功用就是選擇dist最小的臨點給下一回合用的， 12/02 12:55
→ mistel: 雖然我不確定dist變數在幹嘛...但v=i這邊就是在做這件事 12/02 12:55