4

这是我正在努力解决的练习考试中的一个问题：

令 G = (V, E) 是一个加权无向连通图，具有正权重（您可以假设权重是不同的）。给定一个实数 r，定义子图 Gr = (V, {e in E | w(e) <= r})。例如，G0 没有边（显然是断开的），Ginfinity = G（假设是连通的）。问题是找到最小的 r 使得 Gr 是连通的。

描述通过重复应用 BFS 或 DFS 来解决问题的 O(mlogn) 时间算法。

真正的问题是在 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) 的任何想法？谢谢！

4

2 回答 2

3

下面的算法怎么样？

首先从图中获取所有边的列表（或所有不同的边长度，使用 ）并对它们进行排序。这需要 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，并检查图形的连通性，仅使用 BFS 或 DFS 的长度 <= r 的边。

二进制搜索的每次迭代都需要 O(m)，并且您必须进行 O(log m)=O(log n) 次迭代。

于 2011-12-15T21:39:07.763 回答
3

您正在迭代所有可能的边缘成本，这会导致 O(m) 的外循环。请注意，如果当您丢弃所有边 >w(e) 时图形断开连接，那么对于 >w(e') where 也断开连接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)) 中完成。

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

于 2011-12-15T21:40:09.607 回答