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

Question

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

但我在 this 的求职面试问题上卡住了当然。

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.

Answer 1

寻找Minimum Bottleneck Spanning Tree的标准算法(MBST) 被称为 Camerini’s algorithm .它以线性时间运行，如下所示:

 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. Median can be found in O(n) .
2. 第7行可以生成disjoint-set使用 BFS 或 DFS 的数据结构。
3. 第 13 行涉及过滤 A 中的边，其中每条边的端点要么在 F 中的两个不同连通分量中，要么一个端点是不在 F 中的顶点而另一个在 F 中，或者两者都不在 F 中。此测试可以是使用有效的不相交集数据结构在 O(1) 摊销时间内为每条边完成。

更新:我现在还创建了 Wikipedia page关于这个话题。