为什么克鲁斯卡尔算法可以贪心地寻找最小生成树呢?难道最小生成树不是一个全局最优化问题吗? 贪心的目的不就是有可能无法找到最优解吗?那么克鲁斯卡尔算法如何能够在贪心的同时找到最小生成树呢?
S
,最优解为T
。e = (u, v)
出现在S
中而不出现在T
中。由于T
是生成树,因此节点u
和节点v
之间必定存在一条路径。u-v
上至少有一条边的权重不小于e
。否则,Kruskal算法会选择路径u-v
上的所有边而不是边e
。e
添加到解T
中,解决方案将不会变得更糟。并且由于我们假设T
是最优的,经过这个改变后,树依然是最优的。如果我们反复应用这种逻辑,我们总是能够使S
变得最优。有一些贪心算法可以产生全局最优解,也有一些贪心算法不行。Kruskal算法恰好属于第一类(需要像其他答案中所示的标准证明)。
我不确定你的意思。
然而,维基百科说:
Kruskal算法是一种最小生成树算法,它找到连接森林中任意两棵树的最小可能权重的边。[1] 它是图论中的贪心算法,因为它在每个步骤中添加增加成本的弧来查找连接加权图的最小生成树。[1] 这意味着它找到了一个包括每个顶点的树的边的子集,其中树中所有边的总权重最小。如果图不连通,则它会找到一个最小生成森林(每个连通分量的最小生成树)。
同时,关于最小生成树,维基百科说:
最小生成树(MST)或最小权重生成树是连接所有顶点的连通的、边带权无向图的边的子集,没有任何循环,并且具有最小可能的总边权。也就是说,它是一棵跨度树,其边权之和尽可能小。更一般地,任何无向图(不一定连通)都有一个最小生成森林,它是其连通分量的最小生成树的并集。
因此,结合这两个定义:Kruskal基本上使用贪心搜索方法找到最小生成树或森林。