algorithm - 找到具有相同权重的最大边数的生成树

Question

问题来了。

给定一个带权无向连通图G。权重是恒定的。任务是想出一个算法来找到满足这两个条件的 G 生成树的总权重(按优先级排序):

• 生成树必须有相同权重的最大边数(实际重复的权重值无关紧要)；
• 总生成树权重应该最小化。这意味着，例如，权重为 120 的生成树 T1 最多有 4 条具有相同权重的边(以及每条边的权重这四个是 15) 应该优于权重为 140 的生成树 T2，它最多有 4 个边具有相同的权重(并且这四个中的每一个的权重都是 8)。

我已经坚持了很长一段时间了。我已经为图实现了 Boruvka 的 MST 搜索算法，现在我不确定是否应该在找到 MST 后执行任何操作，或者修改 MST 搜索算法本身会更好。

欢迎提出任何建议!

Answer 1

这可以在 O(m^2) 中简单地完成，并且在 O(mn) 中不需要太多努力。似乎可以更快地完成它，可能像 O(m log^2(n)) 甚至 O(m log(n)) 与一点点工作。

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

这个问题的解决方案是 MST(k) 对于一些 k。因此，天真的解决方案是生成所有 MST(k) 并选择具有最大数量的相同边权重然后最小总权重的那个。使用 Kruskal 算法，您可以在 O(m^2) 中执行此操作，因为您只需对边缘进行一次排序。

这可以改进为 O(mn)，首先使用原始权重找到 MST，然后对于每个 k，将树修改为 MST (k) 通过将权重k 的每条边的权重减小到-Infinity。更新 MST 以减少边权重是一个 O(n) 操作，因为您只需要在相应的 fundamental cycle 中找到最大权重边即可.

要使用这种方法比 O(mn) 做得更好，您必须以这样一种方式预处理原始 MST，以便可以更快地执行这些边缘权重减少。好像是 heavy path decomposition 之类的东西应该可以在这里工作，但还有一些细节需要解决。