algorithm - 在克鲁斯卡尔算法上使用贪婪策略时要解决的子问题是什么？

Question

Kruskal 算法在每次迭代中选择最小的边。虽然最终目标是获得 MST，但要解决的子问题是什么？是要得到一个重量最小且完全连接的森林吗？

标签： algorithmgraphtreegreedy

Answer 1

正如在维基百科中我们知道：

Kruskal 算法是一种最小生成树算法，它找到连接森林中任意两棵树的权重最小的边。

...

这意味着它找到了形成包含每个顶点的树的边的子集，其中树中所有边的总权重最小化。

所以 Kruskal 正在寻找最小生成树，但这意味着什么？它正在寻找总成本（权重总和）最小化的树。并且根据最优性原理，我们已经知道最短路径的任何子路径都是其端节点之间的最短路径。

为了更好地回答您的问题，在每次迭代中，您都在寻找最短边来连接两个顶点而不形成循环。