graph - 如何在图中找到最小生成树的总数？

Question

我不想找到所有最小生成树，但我想知道它们中有多少，这是我考虑的方法:

使用 prim 或 kruskal 算法找到一棵最小生成树，然后找到 重量 并在运行计数器等于最小生成树的权重时增加运行计数器。

我找不到任何方法来找到所有生成树的权重，而且生成树的数量可能非常大，因此这种方法可能不适合该问题。
由于最小生成树的数量是指数级的，因此将它们计数并不是一个好主意。

所有的权重都是正的。

我们也可以假设权重不会在图中出现超过 3 次。

顶点数将小于或等于 40,000。

边数将小于或等于 100,000。

图中只有一棵顶点权重不同的最小生成树。我认为找到最小生成树数量的最佳方法必须是使用此属性。

编辑 :

我找到了解决这个问题的方法，但我不确定它为什么有效。任何人都可以请解释一下。

解:求最小生成树长度的问题是众所周知的；寻找最小生成树的两种最简单的算法是 Prim 算法和 Kruskal 算法。在这两者中，Kruskal 的算法按照边缘权重的递增顺序处理边缘。不过，克鲁斯卡尔算法有一个重要的关键点需要考虑:当考虑按权重排序的边列表时，边可以贪婪地添加到生成树中(只要它们不连接已经以某种方式连接的两个顶点)。

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

这两个事实一起意味着我们的答案将是使用 Kruskal 算法插入长度为 K 的边(对于 K 的每个可能值)的方法数量的乘积。由于最多有三个任意长度的边，因此可以对不同的情况进行暴力破解，并且可以像通常那样在每一步之后确定连接的组件。

Answer 1

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

如果您使用 prim 的算法，并将其作为起始边运行在每条边上，并且还使用您遇到的所有关系。然后，您将拥有一个包含 Prim 算法能够找到的所有最小生成树的森林。我不知道这是否等于包含所有可能的最小生成树的森林。

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