1

给定一个权重为 w(e) 的加权无向图 G(v,e)，找到边的集合，使得每对顶点 (u,v)∈G 是连通的（简而言之，spanning tree），并且选择的权重范围边是最小的（或者最小权重和最大权重之间的差是最小的）。

我尝试了贪婪的方法，其中根据权重对边进行排序，然后在排序后的数组中选择连续边之间权重差异最小的两条边（g[index = current_left]，g[index+1 = current_right]），随后我根据 (current_left,current_left- j) 或 (current_right,current_right+ j) 之间的最小差异向左或向右移动，其中j递增直到我们找到具有至少一个未访问顶点的边。

例如：

在此处输入图像描述

这里我们可以得到的最小范围是通过选择权重为 {2,3,5} 的边，范围是 3。

请指出一个建议算法失败的测试用例，并建议一种算法来寻找这种生成树。

编辑：

预期时间复杂度为 O(|E|log|E|) 其中 |E| 是边数。

4

2 回答 2

2

你应该能够做到这一点O(E * (cost of MST computation))：

T = no tree
for all edge weights w_fix sorted in ascending order:
    for all edges e:
        if w(e) >= w_fix:
            set w'(e) = w(e) - w_fix
        else:
            set w'(e) = infinity
    find MST T' according to w'
    if T == no tree or max edge weight(T) > max edge weight(T'):
        set T := T'
print T

这个想法是一些边缘权重必须是最优生成树中边缘之间的最小边缘权重；所以固定一个最小边缘权重并找到一个只包含比这更重的边缘的 MST。由于所有 MST 也是最小瓶颈生成树，因此这将起作用。

这是一个对数平方因子最佳的改进；基本思想保持不变。

sort edge array E[] by increasing weights

low := high := 0
opt_low := opt_high := 0
opt := infinity
connected := false

while (high < E.length - 1) or (connected):

    if not connected:
        high = high + 1
    else:
        low = low + 1

    update(connected)

    if connected:
        if E[high].weight - E[low].weight < opt:
            opt = E[high].weight - E[low].weight
            opt_low = low
            opt_high = high

print(opt, opt_low, opt_high)

这个想法是在边缘上保持一个滑动窗口，并使用连接来维护窗口。要维护连接信息，您将使用特殊的数据结构。其中有许多允许多对数时间成本来维护删除和添加边的连接信息，您可以在这些 MIT 6.851 讲义中找到有关这些数据结构的信息。

于 2015-11-09T12:22:30.863 回答
0

G Bach infact 描述的算法工作正常，运行时间为 O(m*m)，其中 m 是边数（考虑到 mst 的计算需要 O(m) 时间）。这是在 codeforces edu 部分提出的问题。

于 2021-02-01T12:38:53.883 回答