为什么Kruskal算法是贪心的却能找到最小生成树？

Question

为什么克鲁斯卡尔算法可以贪心地寻找最小生成树呢？难道最小生成树不是一个全局最优化问题吗？ 贪心的目的不就是有可能无法找到最优解吗？那么克鲁斯卡尔算法如何能够在贪心的同时找到最小生成树呢？

- DiderDrogba344

Answer 1

好的，假设您说得对，那么Kruskal算法将无法找到最优解。令Kruskal算法找到的解为S，最优解为T。

必定存在一条边e = (u, v)出现在S中而不出现在T中。由于T是生成树，因此节点u和节点v之间必定存在一条路径。

现在，我们应该注意到路径u-v上至少有一条边的权重不小于e。否则，Kruskal算法会选择路径u-v上的所有边而不是边e。

这意味着，如果我们删除那条边并将e添加到解T中，解决方案将不会变得更糟。并且由于我们假设T是最优的，经过这个改变后，树依然是最优的。如果我们反复应用这种逻辑，我们总是能够使S变得最优。

- miheyan

---

否则，Kruskal算法将选择路径u-v上的所有边而不是边e。我不清楚为什么这一点必须成立。例如，可能存在另一条路径。我认为维基百科上的正确性证明更容易理解。 - John Jiang

Answer 2

我能理解提问者的问题是： 贪心算法并不总是最优的，那么为什么Kruskal算法可以得到最优解？ 这个问题可以分两部分回答：

1. Kruskal算法是否能给出最优解？ 这已经被@miheyan回答了。

2. 贪心算法是否总是能给出最优解？ 通常情况下，贪心算法并不能总是给出最优解。但是有一类问题适合用贪心算法来解决，并且Kruskal算法正好属于这一类问题。

我们来看一个问题描述： 有两个玩家（玩家A和玩家B）同时拿到一堆面额不同的纸币，比如4张钞票，面值分别为100元、50元、20元和10元。两名玩家将轮流选择一张钞票，由A先手开始，直到所有纸币都被选完。获得总价值更高的玩家获胜。两人都会采取最优策略。请问谁会赢得游戏？

现在尝试使用贪心策略来解决这个问题，并查看贪心策略是否能够得出最优解。可以尝试不同的数值和例子来进行实验。

因此，底线是- 对于一组问题，贪心解决方案始终是最优的，但并非适用于所有问题。希望这有所帮助！

- CNatka

Answer 3

有一些贪心算法可以产生全局最优解，也有一些贪心算法不行。Kruskal算法恰好属于第一类（需要像其他答案中所示的标准证明）。

- Daniel R. Collins

---

这并没有回答问题。 - undefined

鉴于原帖提出了4个问题，本回答将重点解答其中概念上至关重要的第三个问题。 - undefined

据我所了解，楼主已经假设了克鲁斯卡尔算法是正确的，并且根据问题的标题，我猜想问题的本质是在质疑这个算法为什么会有效果，尽管它是贪婪算法。 - undefined

Answer 4

我不确定你的意思。

然而，维基百科说：

Kruskal算法是一种最小生成树算法，它找到连接森林中任意两棵树的最小可能权重的边。[1] 它是图论中的贪心算法，因为它在每个步骤中添加增加成本的弧来查找连接加权图的最小生成树。[1] 这意味着它找到了一个包括每个顶点的树的边的子集，其中树中所有边的总权重最小。如果图不连通，则它会找到一个最小生成森林（每个连通分量的最小生成树）。

同时，关于最小生成树，维基百科说：

最小生成树（MST）或最小权重生成树是连接所有顶点的连通的、边带权无向图的边的子集，没有任何循环，并且具有最小可能的总边权。也就是说，它是一棵跨度树，其边权之和尽可能小。更一般地，任何无向图（不一定连通）都有一个最小生成森林，它是其连通分量的最小生成树的并集。

因此，结合这两个定义：Kruskal基本上使用贪心搜索方法找到最小生成树或森林。

- Ehsan