如何计算最低瓶颈线性时间生成树？ [英] How to compute a minimum bottleneck spanning tree in linear time?

问题描述

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

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

  

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

解决方案

1. 获取 V 中，权重的中值| E |边缘。
2. 找到所有边缘的值不大于 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.

解决方案

1. Get V, the median of the weights of the |E| edges.
2. 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)

这篇关于如何计算最低瓶颈线性时间生成树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！