Kruskal算法采用贪心策略解决的子问题是什么？
What is the sub-problem being solved when greedy strategy is used on Kruskal's algorithm?
Kruskal 算法在每次迭代时选择最小的边。虽然最终目标是获得 MST，但要解决的子问题是什么？是不是要得到一个权重最小且全连接的森林？
正如我们在维基百科中所知道的那样：
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.
...
This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
所以 Kruskal 正在寻找最小生成树，但这意味着什么？它正在寻找总成本（权重总和）最小化的树。并且根据最优性原理我们已经知道，最短路径的任何子路径都是其端节点之间的最短路径。
为了更好地回答您的问题，在每次迭代中您都在寻找连接两个顶点而不形成循环的最短边。
在算法的每一步，您都有给定数量的边，k，以及 (a) 可以由 k 条边。在最后一次迭代之后，该森林实际上将是一棵树。那片森林仍然有那个 属性：它是一个最小权重的森林，可以由 n-1 条边组成。
由于它也是一棵树，并且由于它必然包括图中的所有节点（因为没有循环），因此它也是一棵最小生成树。
Kruskal 算法在每次迭代时选择最小的边。虽然最终目标是获得 MST，但要解决的子问题是什么？是不是要得到一个权重最小且全连接的森林？
正如我们在维基百科中所知道的那样：
Kruskal's algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.
...
This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.
所以 Kruskal 正在寻找最小生成树，但这意味着什么？它正在寻找总成本（权重总和）最小化的树。并且根据最优性原理我们已经知道，最短路径的任何子路径都是其端节点之间的最短路径。
为了更好地回答您的问题，在每次迭代中您都在寻找连接两个顶点而不形成循环的最短边。
在算法的每一步，您都有给定数量的边，k，以及 (a) 可以由 k 条边。在最后一次迭代之后，该森林实际上将是一棵树。那片森林仍然有那个 属性：它是一个最小权重的森林，可以由 n-1 条边组成。
由于它也是一棵树，并且由于它必然包括图中的所有节点（因为没有循环），因此它也是一棵最小生成树。