如何计算最低瓶颈线性时间生成树？

问题描述

我们可以找到一个瓶颈最小生成树为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.

解决方案

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)

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