在给定图中查找具有最小范围的生成树的算法

Question

给定一个权重为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|是边数。

Answer 1

你应该可以在 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 也是 minimum bottleneck spanning trees，这将起作用。

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

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)

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

Answer 2

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

在给定图中查找具有最小范围的生成树的算法

Algorithm for finding spanning tree with minimum range in a given graph

algorithm

graph

range

minimum

spanning-tree