Graphic Minimal Spanning Tree Using BFS

Question

This is a problem with a practice exam that I am struggling with:

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

Describe the O (mlogn) -time algorithm that solves the problem of repeated BFS or DFS applications.

The real problem is doing this in O (mlogn). Here is what I have:

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 

This is a colossal O (m ^ 2 + mn). Any ideas for bringing it to O (mlogn)? Thanks!

Answer 1

You iterate over all possible costs to the edges, which leads to an outer O (m) loop. Note that if the graph is disabled when all edges> w (e) are dropped, it is also disabled for> w (e '), where w(e') < w(e) . You can use this property to perform a binary search at the cost of an edge and thus do it 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 

Binary search has complexity O (log (max_e-min_e)) (you can actually bring it to O (log (edges)), and dropping 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 errors. But the idea should work.

Answer 2

What about the following algorithm?

First, take a list of all edges (or all different edge lengths using) from the graph and sort them. This takes O (m * log m) = O (m * log n) time: m is usually less than n ^ 2, so O (log m) = O (log n ^ 2) = O (2 * log n) = O (log n).

Obviously, r must be equal to the weight of some edge. This way you can perform a binary search on the edge index in a sorted array.

For each pointer that you try, you take the length of the corresponding edge as r and check the graph for the connection, using only edges of length <= r with BFS or DFS.

Each iteration of a binary search takes O (m), and you must iterate O (log m) = O (log n).