6
我不想找到所有最小生成树，但我想知道有多少人在那里，这里是我所考虑的方法：如何查找图中最小生成树的总数？
- 采用古板的或者Kruskal算法和查找一个最小生成树然后找到所有生成树的权重，并在运行计数器等于最小生成树的权重时增加运行计数器。
我找不到任何方法来发现所有的生成树，也生成树的数量可能是非常大的权重，因此这种方法可能不适合的问题。 由于最小生成树的数量是指数，所以数它们不会是一个好主意。
- 所有的权重将是积极的。
- 我们还可以假设，没有重将在图形显示的三倍以上。
- 顶点的数量将小于或等于40,000。
- 边数将小于或等于100,000。
图中只有一个最小生成树，其顶点权重不同。我认为找到最小生成树数的最好方法必须是使用这个属性的东西。
编辑：
我找到了解决这个问题，但我不知道，为什么它的工作原理。任何人都可以请解释它。
解决方案：找到最小生成树的长度的问题是相当知名;寻找最小生成树的两个最简单的算法是Prim算法和Kruskal算法。在这两个中，Kruskal的算法按照权重的升序来处理边缘。然而，克鲁斯卡尔算法需要考虑的一个重要关键点是：当考虑按权重排序的边缘列表时，边缘可以被贪婪地添加到生成树中（只要它们不连接已经以某种方式连接的两个顶点）。
现在考虑使用Kruskal算法部分形成生成树。我们插入了一些长度小于N的边，现在必须选择长度为N的多个边。算法规定，如果可能，我们必须在长度大于N的任何边之前插入这些边。但是，我们可以以我们想要的任何顺序插入这些边缘。另请注意，无论我们插入哪条边，它都不会改变图的连通性。 （让我们考虑两个可能的图，一个从顶点A到顶点B有一个边，另一个没有，第二个图必须有A和B作为同一连通分量的一部分;否则从A到B的边将被插入一点）
这两个事实一起意味着我们的答案将是使用Kruskal算法插入长度为K（对于K的每个可能值）的边的数量的乘积。由于任意长度的边至多有三个边，所以不同的情况可以是强制性的，并且可以在每一步之后确定连接的部件，正如他们通常那样。
我试图解决的问题具有高达100,000的边缘。所以从每个边缘运行prim算法将需要很长时间。 – 2147483647
您可以通过检查是否有任何中间图是您已经作为中间图遇到的图来加速它。任何这样的图形肯定会产生我们已有的最小生成树。尽管这会让你记忆。无论如何，它将保持缓慢。 – bowmore
您可以同时为每个起始边缘运行算法：首先制作Prim算法中第一步结果的所有树木的森林。 （从40k顶点产生abt.2万棵树）然后在该森林中的每棵树上执行该算法的下一步，并创建一个包含具有两条边的树的新森林（可能删除更多副本）。每个步骤都会继续消除重复项，并且该结构还可以轻松地处理多种可能性，作为下一步将所有可能性添加到下一代森林 – bowmore