使用BFS算法生成图的最小生成树

Question

这是一道关于it技术的练习考试题，我正在努力解决：

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

请描述一种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)吗？谢谢！

- Garrett

Answer 1

以下算法怎么样？

首先，从图中获取所有边（或所有不同的边长，使用）列表并对其进行排序。这需要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)次迭代。

- Kolmar

---

我认为我们不能假设 m < n^2，因此这是 O(mlogm + (m+n)logm) = O((m+n)logm)。 - Garrett

@Garrett- 你可以假设 m <= n^2，因为对于任何一对边，它们之间最多只有一条边。 - templatetypedef

Answer 2

你正在遍历所有可能的边缘成本，这导致外部循环为O(m)。请注意，如果图形是不连通的，则当你丢弃所有边> w（e）时，它也会在> w（e'）处断开连接，其中w（e'）

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))内完成。

警告：我尚未在代码中测试过这个想法，因此可能会存在错误。但是这个思路应该是可行的。

- MAK

---

这已经好多了，但是O((m+n)logm)仍然比O(mlogn)大。因为logm > logn，所以差别很大。就快成功了！ - Garrett

实际上，O((m + n)log m) = O(m log n)。因为n = O(m)，所以m + n = O(m)。另外，由于m = O(n^2)，O(log m) = O(log (n^2)) = O(2 log n) = O(log n)。因此，O((m + n)log m) = O(m log n)。 - templatetypedef