如何计算线性时间内的最小瓶颈生成树？

  • Z时代
  • 2024-01-10
  • 分类：问答

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

但是我在这门课程中遇到了这个求职面试问题。

即使在最坏的情况下，我们如何在线性时间内找到最小的瓶颈生成树。注意，我们可以假设在最坏的情况下，我们可以计算线性时间中n个键的中位数。

回答：

  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）

以上是 如何计算线性时间内的最小瓶颈生成树？ 的全部内容， 来源链接： utcz.com/qa/420709.html

回到顶部