[其他] 最小成本擴張樹(Kruskal)

看板Math作者 (選ばれし子どもたち)時間4年前 (2021/05/23 14:57), 4年前編輯推噓3(3推 0噓 2→)
留言5則, 2人參與, 4年前最新討論串1/1
如圖所示 https://imgur.com/a/stiLyaS 請問第二小題 右邊參考公職王解答， 看不太懂紅色底線的意思， 中間圖樹我依照解答畫出 第6、7點，分支0-3將含4段連線...這段話看不太懂 希望神人解釋 或是可能解答有誤， 跪求神人解惑 我知道Kruskal是依序加入最小邊，但不能有迴圈 可是第二小題條件看不是很懂 願奉上300P感謝幫忙 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.121.236.146 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1621753058.A.122.html
推
05/23 15:01, 4年前 , 1F
0分出去的任何一條都叫分支 一個分支最多三條線
05/23 15:01, 1F
跪求大大可以畫圖幫助我理解 還是聽不太懂 ※ 編輯: ooww (122.121.230.234 臺灣), 05/23/2021 16:55:01
推
05/23 17:00, 4年前 , 2F
0-3-2-1 是一個分支
05/23 17:00, 2F
→
05/23 17:00, 4年前 , 3F
0-4-5-6是一個分支
05/23 17:00, 3F
推
05/24 05:48, 4年前 , 4F
在到 20 那條邊時, 如果加進去則從 0 出發往 3 這邊
05/24 05:48, 4F
→
05/24 05:48, 4年前 , 5F
將有 0-3 3-2 2-1 2-6 四個連線, 不合條件
05/24 05:48, 5F
感謝解惑 另外請教您， 題目說起始節點0， 若起始節點改為2或3或4， 結果是否一樣沒變? ※ 編輯: ooww (218.166.99.191 臺灣), 05/25/2021 02:20:29
‣ 更多 ooww 的文章
文章代碼(AID): #1WgVpY4Y (Math)