由网友(风雨兼程)分享简介：我们可以找到一个瓶颈最小生成树为O（E日志* V）在最坏的情况下，通过使用Kruskal算法。这是因为每一个最小生成树是最起码的瓶颈生成树。 不过，我就死在从这个的过程。我们如何才能找到一个最小的瓶颈，即使在最坏的情况下生成树的线性时间。请注意，我们可以假设，我们可以计算个密钥的中值线性时间在最坏的情况下解决方案 获...

我们可以找到一个瓶颈最小生成树为O（E日志* V）在最坏的情况下，通过使用Kruskal算法。这是因为每一个最小生成树是最起码的瓶颈生成树。

不过，我就死在从这个的过程。

  

我们如何才能找到一个最小的瓶颈，即使在最坏的情况下生成树的线性时间。请注意，我们可以假设，我们可以计算个密钥的中值线性时间在最坏的情况下

解决方案 获取 V 中，权重的中值| E |边缘。 找到所有边缘的值不大于 V 更多，并获得子图 如果该子连接， V 是答案的上限，并降低 V ，重复在步骤1，2。 如果子图没有连接，让连接的组件成为一个节点，并增加 V ，重复第1步，2

然后就可以解决线性时间的问题。

PS：使用DFS来判断子相连。与复杂度为O（E / 2）+ O（E / 4）+ O（E / 8）+ ... = O（E）

We can find a minimum bottleneck spanning tree in O(E log*V) in the worst case by using Kruskal's algorithm. This is because every minimum spanning tree is a minimum bottleneck spanning tree.

But I got stuck on this job-interview question from this course.

How can we find a minimum bottleneck spanning tree in linear time even in the worst case. Note that we can assume that we can compute the median of n keys in linear time in the worst case.

解决方案

Get V, the median of the weights of the |E| edges. Find all edge's value no more than V, and get the subgraph If the subgraph is connected, V is the upper limit of the answer, and decrease the V, repeat the step 1, 2. If the subgraph is not connected, let the connected component to become a node, and increase the V, repeat the step 1, 2.

Then you can solve the question in linear time.

PS: Using DFS to judge the subgraph is connected. and the complexity is O(E/2) + O(E/4) + O(E/8) + ... = O(E)