最近从线上课程复习 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

原来如此，看来我从根本上就搞错了，谢谢楼上几位的说明！