[問題] krsukal 跟 prim's algorithm

看板Prob_Solve作者 (32767)時間7年前 (2016/08/23 00:07), 7年前編輯推噓3(3013)
留言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
文章代碼(AID): #1NkoDVaa (Prob_Solve)