→ dreamroyc:同學推~ 02/11 17:21
※ 引述《tool11 (:))》之銘言：
: 題目 在這
: http://www.postimage.org/image.php?v=aV1g5Cz0
: 以n-1條線結束
: 所以為 6 條
: 為(0,1) (1,2) (0,3) (0,4) (2,6) (4,5)
: 這應該算是a小題吧
: 那b小題是指變成雙向的嗎?
: 那這樣其實結果不也是跟第一題一樣嗎
(a)
我依Prim's algorithm結果是 (以下為依序建立)
(0,3) (2,3) (1,2) (0,4) (2,6) (5,6)
如果權重沒看錯 , 一開始 (0,1) (0,3) (0,4) ,權重分別為 16 12 18
不會選擇到(0,1)才對 , 是(0,3)
依照Prim's algo
" 由現有的頂點集合 , 去選擇最小的連結邊 "
(b)
由於 "一個頂點限制最多兩個連結"
那麼剛剛依照Prim's algo所建立的圖形 , 在頂點 2 就產生問題 (branch > 2)
因為有 (2,3) (2,6) (1,2)
甚至在此條件下 , 頂點 3 , 也連帶發生問題
為了避免這樣情形發生 , 且在branch <= 2之下,產生另一個圖形 (以下為依序建立)
(0,3) (2,3) (1,2) (0,4) (4,5) (5,6)
手頭上沒書,也有一陣子沒碰了 , 有錯在討論看看:)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.51