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

Question

在最坏的情况下,我们可以通过使用Kruskal算法找到O(E log*V)中的最小瓶颈生成树.这是因为每个最小生成树都是生成树的最小瓶颈.

但是我在这个课程中遇到了这个面试问题.

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

Answer 1

查找最小瓶颈生成树(MBST)的标准算法称为Camerini算法.它以线性时间运行,如下所示:

 1. Find a median edge weight in graph and partition all edges in to two
    partitions A and B around it. Let A have all edges greater than
    pivot and B has all edges less than or equal to pivot.                
 2. Run DFS or BFS on partition B. If it connected graph then again run
    step 1 on it.        
 3. If partition B wasn't a connected graph then we must have more than
    1 connected components in it. Create a new graph by contracting each
    of these connected components as a single vertex and select edges
    from partition A that connects these components. MBST is given by
    edges in connected components + MBST of new graph.

在伪代码中:

1:  procedure MBST(V, E)
2:      if |E| = 1 then
3:          Return E 
4:      else
5:          A, B ?  Partition E in two halves around median
6:                  A is higher half, B is lower half
7:          F ? Connected components of B
8:          if |F| = 1 and spans all vertices then
9:              Return MBST(V, B)
10:         else
11:             V' ? create one vertex for each connected component in F
12:                     plus vertices missing from F
13:             B' ? Edges from A that connects components in F
14:                     and edges to vertices not in F
15:             Return F ? MBST(V', B') 
16:         end if
17:     end if
18: end procedure

实施说明:

1. 中位数可以在O(n)中找到.
2. 第7行可以使用BFS或DFS 生成不相交的数据结构.
3. 第13行涉及滤除A中的边缘,其中每条边都有端点,这些端点位于F中的两个不同的连通分量中,或者一个端点的顶点不在F中,而另一个在F中,或者两者都不在F中.这种测试可以使用有效的方法完成O(1)每个边缘的摊销时间中的不相交数据结构.

更新:我现在还在此主题上创建了维基百科页面.

Answer 2

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)