使用 BFS 绘制最小生成树图

Question

这是我在练习考试中遇到的一个问题：

设 G = (V, E) 为带权无向连通图，其中正 权重（您可以假设权重是不同的）。给定一个真实的 数字 r，定义子图 Gr = (V, {e in E | w(e) <= r})。为了 例如，G0 没有边（显然是断开的），并且 Ginfinity = G （根据假设是相连的）。问题是要找到 使 Gr 连通的最小 r。

描述一个 O(mlogn) 时间算法，该算法通过以下方式解决该问题 重复应用BFS或DFS。

真正的问题是在 O(mlogn) 内完成它。这就是我得到的：

r = min( w(e) )                            => O(m)
while true do                              => O(m) 
  Gr = G with edges e | w(e) > r removed     => O(m)
  if | BFS( Gr ).V | < |V|                   => O(m + n)
    r++ (or r = next smallest w(e))          
  else
    return r

这是一个巨大的 O(m^2 + mn)。有什么想法可以将其降低到 O(mlogn) 吗？谢谢！

Answer 1

您正在迭代所有可能的边缘成本，从而产生 O(m) 的外循环。请注意，如果在丢弃所有边 >w(e) 时图已断开连接，则对于 >w(e') 也将断开连接，其中 w(e') w(e') w(e)。您可以使用此属性对边缘成本进行二分搜索，从而在 O(log(n)) 中完成此操作。

lo=min(w(e) for e in edges), hi=max(w(e) for e in edges)
while lo<hi:
   mid=(lo+hi)/2
   if connected(graph after discarding all e where w(e)>w(mid)):
       lo=mid
   else:
       hi=mid-1
return lo

二分搜索的复杂度为 O(log (max_e-min_e)) （实际上可以将其降低到 O(log(edges))，并且丢弃边并确定连通性可以在 O(edges+vertices) 中完成，所以这可以在 O((edge+vertices)*log(edges)) 中完成。

警告：我还没有在代码中对此进行测试，因此可能存在错误，但这个想法应该可行。

Answer 2

下面的算法怎么样？

首先从图中获取所有边（或所有不同边长度，使用 ）的列表并对它们进行排序。这需要 O(m*log m) = O(m*log n) 时间：m 通常小于 n^2，因此 O(log m)=O(log n^2)=O(2*log n) =O(log n)。

显然r应该等于某些边的权重。因此，您可以对排序数组中的边索引进行二分搜索。

对于您尝试的每个索引，您将相应边的长度作为 r，并检查图形的连通性，仅使用长度 <= r 的边与 BFS 或 DFS。

二分查找的每次迭代都需要 O(m)，并且必须进行 O(log m)=O(log n) 次迭代。