在給定圖中尋找具有最小範圍的生成樹的算法

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的信息。