寻找具有相同权值的最大边数的生成树

Question

问题来了。

给出了一个加权无向连通图G。重量是不变的。任务是提出一个算法，该算法将找到满足以下两个条件的生成树的总权重（按优先级排序）：

• 生成树必须具有相同权重的最大边数（实际重复权重值与此无关）；
• 总生成树权重应最小化。这意味着，例如，权重为120的生成树T1最多有4条相同权重的边（这四条边中的每一条的权重都是15）应该优于权重为140的生成树T2，这四条边最多有4条相同权重的边（这四条边中的每一条的权重都是8）。

我已经被困在这个问题上好一阵子了。我已经为图实现了Boruvka的MST搜索算法，现在我不确定是否应该在找到MST后执行任何操作，或者最好修改MST-search算法本身。

Answer 1

这可以在O(m^2)中简单地完成，而在O(mn)中无需太多努力。似乎可以更快地完成这一任务，例如O(m log^2(n))或O(m log(n))只需做一点工作。

基本思想是这样的。对于任何权值k，设MST(k)是一个生成树，它包含权值k的最大可能边数，否则总权值最小。可能有多棵这样的树，但它们都会有相同的总重量，所以你选择哪一棵并不重要。MST(k)可以通过使用任何MST算法并将权k的所有边视为权-无穷大来找到。

对于某些k，此问题的解决方案是MST(k)。因此，简单的解决方案是生成所有MST(k)，并选择相同边权值最大的边权值，然后选择总权值最小的边权值。使用Kruskal的算法，您可以在O(m^2)中完成此操作，因为您只需对边排序一次。

这可以改进为O(mn)，方法是首先使用原始权重查找MST，然后对于每个k，通过将权重k的每个边的权重减少为-infinity，将树修改为MST(k)。更新MST以减少边缘权重是一个O(n)操作，因为您只需要在相应的基本周期中找到最大权重边缘。

要使用这种方法比O(mn)做得更好，您必须对原始MST进行预处理，以便能够更快地执行这些边权重降低。看起来像一个沉重的路径分解应该在这里工作，但有一些细节需要解决。