c++ - 如何使用 union-find、minheap、Kruskal 和排序算法来创建最小成本生成树？ (C++)

Question

如果这个问题有点宽泛，我深表歉意，但我很难理解如何创建最小成本生成树。如果重要的话，这是在 C++ 中。

据我了解，您将使用 Kruskal 来选择用于构建生成树的最小成本边。我的想法是将边缘读入一个最小堆，这样你就可以从顶部移除，以便以最小的成本获得边缘。

到目前为止，我只能实现 minheap 和 union-find 集合，我仍然不确定 union-find 的目的和用于创建生成树的排序算法。

如果有任何建议，我将不胜感激。

编辑:我不限于 union 查找、minheap、kruskals 和排序算法，我也不需要做任何事情。这些只是导师建议的项目。

Answer 1

这两个结构在算法中有不同的用途。 Kruskal 算法的工作原理是在不形成循环的每个点处添加尽可能便宜的边。可以使用一些不是特别复杂的数学来证明这保证了生成的生成树是最小的。其工作原理背后的直觉如下。假设 Kruskal 算法不是最优的，并且存在更便宜的生成树。按权重对该树中的所有边进行排序，然后将这些边按排序顺序与 Kruskal 算法按排序顺序选择的边进行比较。由于我们自相矛盾地假设 Kruskal 的算法不是最优的，因此序列中一定存在不一致的地方。如果在这种分歧中，Kruskal 算法具有比最优解更轻的边缘，那么我们可以通过添加该边缘，找到它创建的循环，然后删除循环中最重的边缘来使最优解更好。该边不能是我们刚刚添加的边，否则会在 Kruskal 算法生成的 MST 中创建一个循环，而 Kruskal 算法永远不会添加创建循环的边。所以这意味着 Kruskal 的算法一定是因为没有添加一些光边而偏离了最优解。但是 Kruskal 算法跳过边的唯一原因是它是否创建了一个循环，这意味着最优 MST 中必须有一个循环，这也是一个矛盾。这意味着我们的假设是错误的，Kruskal 算法必须是最优的。

希望这能激发 Kruskal 算法需要堆和 union 查找结构的原因。我们需要堆，以便我们可以按排序顺序取回所有边缘。如果我们不按此顺序访问边缘，则上述证明将失效并且所有赌注都将取消。有趣的是，您实际上并不需要堆；您只需要某种方式来按排序顺序访问所有边缘。如果需要，您可以将所有边转储到一个巨大的数组中，然后对数组进行排序。如果您使用快速排序，这不会改变二进制堆情况下算法的运行时间。

union-find 结构有点棘手。在 Kruskal 算法中的每个点，您都需要能够判断添加一条边是否会在图中创建一个循环。一种方法是存储一个结构，该结构跟踪哪些节点已经相互连接。这样，在添加边时，您可以检查端点是否已经连接。如果是，则边缘将形成一个循环，应该被忽略。 union-find 结构是一种有效维护此信息的方法。特别是，它的两个操作 - 并集和查找 - 对应于将先前未连接的两个不同的节点组连接在一起的行为，如果您添加一条边以连接生成的不同部分中包含的两棵树，就会出现这种情况森林。查找步骤为您提供了一种检查两个节点是否已连接的方法；如果是这样，你应该跳过当前边缘。

希望这对您有所帮助!