如何求图中最小生成树的总数？

Question

null

• 所有权重都将为正值。
• 我们还可以假设没有权重在图中出现超过三次。
• 顶点数将小于或等于40,000。
• 边数将小于或等于100,000。

在顶点权重不同的图中只有一棵最小生成树。我认为找到最小生成树数目的最好方法一定是使用这个属性。

编辑：

现在考虑一个使用Kruskal算法的部分形成的生成树。我们已经插入了一些长度小于N的边，现在必须选择几条长度为N的边。算法规定，如果可能的话，我们必须在任何长度大于N的边之前插入这些边。然而，我们可以按照我们想要的任何顺序插入这些边。还要注意，无论我们插入哪条边，它都不会改变图的连通性。（让我们考虑两个可能的图，一个图有从顶点A到顶点B的边，另一个图没有。第二个图必须有A和B作为同一连通分量的一部分；否则从A到B的边就会插在一点上。）

这两个事实一起意味着，我们的答案将是使用Kruskal算法插入长度为K的边（对于K的每个可能值）的方法的乘积。由于任意长度的边最多有三条，不同的情况可以被野蛮强迫，并且在每一步之后可以像通常一样确定连接的分量。

Answer 1

看Prim的算法，它说重复添加权重最低的边。如果有一个以上的具有最低权重的边可以添加，会发生什么？选择一棵树可能会比选择另一棵树产生不同的树。

如果你使用Prim的算法，并运行它为每一个边缘作为开始边缘，也锻炼所有的联系，你遇到。然后你就会有一个包含Prim算法能够找到的所有最小生成树的森林。我不知道这是否等于包含所有可能的最小生成树的森林。

这仍然归结为找到所有最小生成树，但我看不出简单的方法来确定不同的选择是否会产生相同的树。