在给定图中求最小值域生成树的算法

Question

给出加权无向图G（v,e）的权值为w（e）,求出使每对顶点(u,v)∈G连通（简言之为生成树)且所选边的权值范围最小（或最小权值与最大权值之差最小）的边集。

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

例如：

Answer 1

您应该能够在O(E*（MST计算的成本）):

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只包含比该权重更重的边缘。因为所有的MSTs也是最小瓶颈生成树，所以这是可行的。

这里有一个改进，在对数平方因子下是最佳的；基本思想不变。

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)

这个想法是在边缘上保持一个滑动窗口，并使用连通性来维护窗口。为了维护连接性信息，您将使用特殊的数据结构。其中有许多数据结构允许多对数的时间开销来维护删除和添加边的连通性信息，你可以在MIT6.851课堂讲稿中找到这些数据结构的信息。