Graph Minimum Spanning Tree using BFS

Question

This is a problem from a practice exam that I'm struggling with:

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.

The real problem is doing it in O(mlogn). Here's what I've got:

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

That's a whopping O(m^2 + mn). Any ideas for getting it down to O(mlogn)? Thanks!

Answer 1

You are iterating over all possible edge costs which results in the outer loop of O(m). Notice that if the graph is disconnected when you discard all edges >w(e), it is also disconnected for >w(e') where w(e') < w(e). You can use this property to do a binary search over the edge costs and thus do this in 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

The binary search has a complexity of O(log (max_e-min_e)) (you can actually bring it down to O(log(edges)) and discarding edges and determining connectivity can be done in O(edges+vertices), so this can be done in O((edge+vertices)*log(edges)).

Warning: I have not tested this in code yet, so there may be bugs. But the idea should work.