PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] krsukal 跟 prim's algorithm

看板Prob_Solve (計算數學 Problem Solving)作者 (32767)時間8年前 (2016/08/23 00:07), 8年前編輯推噓3(3推 0噓 13→)
留言16則, 3人參與, 最新討論串1/1
最近從線上課程複習 minimum spanning tree 時 不免俗地學到了這兩個 prim 跟 kruskal 這兩個著名的演算法 然後有課程有一題的題目是問 "maximum" spanning tree 其中一個方法是把兩個算法反過來用，就是我們不從權重最小的邊開始取 而是從權重最大的邊開始取，但這樣的方法不保證能做出最大生成樹 題目：http://imgur.com/CB3ctOl
但是如果是如推文的方法，把所有邊的權重都乘上-1，然後一樣 求最小生成樹，就可以得到最大生成樹了 題目：http://imgur.com/6NkoYEk
想請問一下有沒有可以參考的證明，或是有高手願意提示一下為什麼會 這樣呢？ 謝謝！ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.46.159.162 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1471882079.A.924.html
推
08/23 01:29, , 1F
不管什麼演算法，每條邊權重乘上-1求最小生成樹，就
08/23 01:29, 1F
→
08/23 01:29, , 2F
會是最大生成樹。如果擔心負權重會有問題，可以同加
08/23 01:29, 2F
→
08/23 01:29, , 3F
一夠大的正數，反正生成樹的邊數一定是點數減一
08/23 01:29, 3F
→
08/23 01:45, , 4F
原來如此，所以是利用求最小生成樹的方法，反求
08/23 01:45, 4F
→
08/23 01:45, , 5F
最大生成樹
08/23 01:45, 5F
→
08/23 01:46, , 6F
那我想問一下為什麼不能反過來做(查到的資料)
08/23 01:46, 6F
→
08/23 01:46, , 7F
例如 kruskal 直接把邊從大排到小，然後每次選最大權重
08/23 01:46, 7F
→
08/23 01:47, , 8F
的邊。這樣做的話生出來的不一定會是最大生成樹
08/23 01:47, 8F
→
08/23 01:48, , 9F
為什麼會這樣呢？實在是想不透...
08/23 01:48, 9F
→
08/23 01:49, , 10F
哪個資料啊? 然後內文說 Prim 不行推文卻說 Kruskal @@?
08/23 01:49, 10F
→
08/23 01:59, , 11F
我修正一下好了，不好意思我內文有講錯的
08/23 01:59, 11F
※ 編輯: johnny94 (114.46.159.162), 08/23/2016 02:05:21
推
08/23 02:20, , 12F
有問題的是 "有向" 不是最小變最大
08/23 02:20, 12F
推
08/23 17:35, , 13F
有向圖中maximum acyclic graph不一定是樹
08/23 17:35, 13F
→
08/23 17:36, , 14F
我以為你在說無向圖，所以才提出乘上-1
08/23 17:36, 14F
→
08/23 18:34, , 15F
原來如此，看來我從根本上就搞錯了，謝謝樓上幾位的說明
08/23 18:34, 15F
→
08/23 18:34, , 16F
！
08/23 18:34, 16F
‣ 更多 johnny94 的文章
文章代碼(AID): #1NkoDVaa (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 johnny94 的文章
文章代碼(AID): #1NkoDVaa (Prob_Solve)