Kruskal的算法如何贪婪？

Question

据说用于MST构造的Kruskal算法是贪婪的，但与Prim算法不同，该算法选择全局最小值而不是局部最小值。有人可以解释如何将Kruskal算法视为贪婪方法吗？

Answer 1

我们在克鲁斯卡尔做什么？首先根据边缘的重量对边缘进行排序。然后我们选择重量最小的边缘。如果没有循环，则添加该边。因此，我们贪婪地前进。所以这是贪婪的做法。 :)

贪婪方法称为贪婪，因为它在期望的每个阶段都进行了最佳选择，从而给出了总体最优解。

Answer 2

这是一个贪婪算法，因为您选择了根据可用的最小权重在每个步骤中合并两组顶点，因此选择了当前看起来最佳的边。这是一个贪婪的步骤，因此该算法被称为贪婪。

在Wikipedia的伪代码中（随附），贪婪步骤由(u,v)选择，这是连接两个未连接组件的最低加权边。

KRUSKAL(G):
1 A = ∅
2 foreach v ∈ G.V:
3   MAKE-SET(v)
4 foreach (u, v) ordered by weight(u, v), increasing:
5    if FIND-SET(u) ≠ FIND-SET(v):
6       A = A ∪ {(u, v)}
7       UNION(u, v)
8 return A

Answer 3

首先，贪婪是什么意思？

贪心算法是遵循问题解决方法的任何算法启发式地在每个阶段做出局部最优选择寻找全局最优的意图。----维基百科https://en.wikipedia.org/wiki/Greedy_algorithm

因此，“贪心算法”是关于按顺序进行选择，以使每个单独的选择都可以根据某些有限的“短期”标准来进行评估，而该标准不太昂贵，无法评估。

在Kruskal的算法中，“选择”是“以次低的权重选择边缘，并且不与已拾取的边缘形成循环”，考虑到排序算法和联合查找数据，进行评估并不太昂贵结构。

您在问题中提到的局部最小值应更多地理解为图形的当前知识，而不是相邻的顶点或边。