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

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 |登录| 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) 

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