如果这个问题有点宽泛，我深表歉意，但我很难理解如何创建最小成本生成树。如果重要的话，这是在 C++ 中。
据我了解，您将使用 Kruskal 来选择构建生成树的最小成本边。我的想法是将边缘读入一个minheap，这样你就可以从顶部移除，以便以最低的成本获得边缘。
到目前为止，我只能为 union-find 实现 minheap 和 sets，我仍然不确定 union-find 的目的和用于创建生成树的排序算法。
我将不胜感激任何建议。
编辑：我不限于联合查找、minheap、kruskals 和排序算法，也不需要我做任何事情。这些只是导师建议的项目。
这两种结构在算法中服务于不同的目的。Kruskal 的算法通过在不形成循环的每个点添加最便宜的可能边来工作。可以使用一些不是特别复杂的数学来证明，这保证了生成的生成树是最小的。其工作原理背后的直觉如下。假设 Kruskal 算法不是最优的，并且存在更便宜的生成树。按权重对该树中的所有边进行排序，然后将这些边按排序顺序与 Kruskal 算法按排序顺序选择的边进行比较。由于我们假设 Kruskal 算法不是最优的矛盾，因此在序列中一定有一些地方存在分歧。如果在这种分歧中，克鲁斯卡尔算法的边缘比最优解更轻，然后我们可以通过添加该边，找到它创建的循环，然后删除循环中最重的边，从而使最佳解决方案变得更好。该边不能是我们刚刚添加的边，否则会在 Kruskal 算法生成的 MST 中创建一个循环，而 Kruskal 算法永远不会添加创建循环的边。所以这意味着 Kruskal 的算法必须通过不添加一些轻边而偏离最优解。但是 Kruskal 算法跳过一条边的唯一原因是它是否创建了一个循环，这意味着最优 MST 中必须存在一个循环，这也是一个矛盾。这意味着我们的假设是错误的，克鲁斯卡尔的算法必须是最优的。然后删除循环中最重的边缘。该边不能是我们刚刚添加的边，否则会在 Kruskal 算法生成的 MST 中创建一个循环，而 Kruskal 算法永远不会添加创建循环的边。所以这意味着 Kruskal 的算法必须通过不添加一些轻边而偏离最优解。但是 Kruskal 算法跳过一条边的唯一原因是它是否创建了一个循环，这意味着最优 MST 中必须存在一个循环，这也是一个矛盾。这意味着我们的假设是错误的，克鲁斯卡尔的算法必须是最优的。然后删除循环中最重的边缘。该边不能是我们刚刚添加的边，否则会在 Kruskal 算法生成的 MST 中创建一个循环，而 Kruskal 算法永远不会添加创建循环的边。所以这意味着 Kruskal 的算法必须通过不添加一些轻边而偏离最优解。但是 Kruskal 算法跳过一条边的唯一原因是它是否创建了一个循环，这意味着最优 MST 中必须存在一个循环，这也是一个矛盾。这意味着我们的假设是错误的，克鲁斯卡尔的算法必须是最优的。s 算法从不添加创建循环的边。所以这意味着 Kruskal 的算法必须通过不添加一些轻边而偏离最优解。但是 Kruskal 算法跳过一条边的唯一原因是它是否创建了一个循环，这意味着最优 MST 中必须存在一个循环，这也是一个矛盾。这意味着我们的假设是错误的，克鲁斯卡尔的算法必须是最优的。s 算法从不添加创建循环的边。所以这意味着 Kruskal 的算法必须通过不添加一些轻边而偏离最优解。但是 Kruskal 算法跳过一条边的唯一原因是它是否创建了一个循环，这意味着最优 MST 中必须存在一个循环，这也是一个矛盾。这意味着我们的假设是错误的，克鲁斯卡尔的算法必须是最优的。
希望这能解释为什么 Kruskal 的算法需要堆和联合查找结构。我们需要堆，以便我们可以按排序顺序取回所有边。如果我们不按这个顺序访问边，那么上面的证明就会失效，所有的赌注都会被取消。有趣的是，您实际上并不需要堆。您只需要某种方式按排序顺序访问所有边缘。如果需要，您可以将所有边转储到一个巨大的数组中，然后对数组进行排序。如果您使用快速排序，这不会改变二进制堆情况下算法的运行时间。
The union-find structure is a bit trickier. At each point in Kruskal's algorithm you need to be able to tell whether adding an edge would create a cycle in the graph. One way to do this is to store a structure that keeps track of what nodes are already connected to one another. That way, when adding an edge, you can check whether the endpoints are already connected. If they are, then the edge would form a cycle and should be ignored. The union-find structure is a way of maintaining this information efficiently. In particular, its two operations - union and find - correspond to the act of connecting together two distinct groups of nodes that were previously not connected, as would be the case if you added an edge that connected two trees contained in different parts of the spanning forest. The find step gives you a way to check if two nodes are already connected; if so you should skip the current edge.
Hope this helps!