这是我正在努力解决的模拟考试问题:
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) 的任何想法?谢谢!
最佳答案
您正在迭代所有可能的边缘成本,这导致 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)) 中完成。
警告:我还没有在代码中对此进行测试,因此可能存在错误。但这个想法应该可行。
关于algorithm - 使用 BFS 绘制最小生成树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8526752/