algorithm - 使用 BFS 绘制最小生成树

Question

这是我正在努力解决的模拟考试问题:

Let G = (V, E) be a weighted undirected connected graph, with positive weights (you may assume that the weights are distinct). Given a real number r, define the subgraph Gr = (V, {e in E | w(e) <= r}). For example, G0 has no edges (obviously disconnected), and Ginfinity = G (which by assumption is connected). The problem is to find the smallest r such that Gr is connected.

Describe an O(mlogn)-time algorithm that solves the problem by repeated applications of BFS or 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) .您可以使用此属性对边成本进行二分搜索，从而在 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)) 中完成。

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