最近從線上課程複習 minimum spanning tree 時
不免俗地學到了這兩個 prim 跟 kruskal 這兩個著名的演算法
然後有課程有一題的題目是問 "maximum" spanning tree
其中一個方法是把兩個算法反過來用，就是我們不從權重最小的邊開始取
而是從權重最大的邊開始取，但這樣的方法不保證能做出最大生成樹
題目：http://imgur.com/CB3ctOl
但是如果是如推文的方法，把所有邊的權重都乘上-1，然後一樣
求最小生成樹，就可以得到最大生成樹了
題目：http://imgur.com/6NkoYEk
想請問一下有沒有可以參考的證明，或是有高手願意提示一下為什麼會
這樣呢？
謝謝！

不管什麼演算法，每條邊權重乘上-1求最小生成樹，就會是最大生成樹。如果擔心負權重會有問題，可以同加一夠大的正數，反正生成樹的邊數一定是點數減一

原來如此，所以是利用求最小生成樹的方法，反求最大生成樹那我想問一下為什麼不能反過來做(查到的資料)例如 kruskal 直接把邊從大排到小，然後每次選最大權重的邊。這樣做的話生出來的不一定會是最大生成樹為什麼會這樣呢？實在是想不透...

哪個資料啊? 然後內文說 Prim 不行推文卻說 Kruskal @@?

我修正一下好了，不好意思我內文有講錯的

有問題的是 "有向" 不是最小變最大

有向圖中maximum acyclic graph不一定是樹我以為你在說無向圖，所以才提出乘上-1

原來如此，看來我從根本上就搞錯了，謝謝樓上幾位的說明！