2

这就是问题所在。

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

  • 生成树必须具有相同权重的最大边数(实际重复的权重值无关紧要);
  • 应该最小化总的生成树权重。这意味着,例如,权重为 120 的生成树 T1 应优先于权重为 140 且权重为大多数 4 条边具有相同的权重(这四个边的权重为 8)。

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

欢迎任何建议!

4

1 回答 1

1

这可以在 中天真地完成O(m^2),并且无需太多努力O(mn)。似乎有可能做得更快,也许是类似的O(m log^2(n)),甚至O(m log(n))是一点点工作。

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

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

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

为了比使用这种方法做得更好O(mn),您必须对原始 MST 进行预处理,以便可以更快地执行这些边缘权重减少。看起来像重路径分解之类的东西应该在这里起作用,但是有一些细节需要解决。

于 2017-10-17T19:18:45.233 回答