How to calculate the minimum spanning tree in linear time?

Question

We can find the minimum spanning tree in O (E log * V) in the worst case using the Kruskal algorithm. This is because each minimum spanning tree is a minimum bottleneck.

But I'm stuck on this job interview from this course.

How can we find the minimum spanning tree in linear time even in the worst case. Note that we can assume that we can calculate the median of n keys in linear time in the worst case.

Answer 1

• Get V , median weights | E | the edges.
• Find all edge values ​​of at most V and get a subgraph
  • If a subgraph is connected, V is the upper limit of the response and decreases V , repeat step 1, 2.
  • If the subgraph is not connected, let the connected component become node and increase V , repeat step 1, 2.

Then you can solve the problem in linear time.

PS: Using DFS, you can judge the subgraph. and complexity O (E / 2) + O (E / 4) + O (E / 8) + ... = O (E)

Answer 2

The standard minimum spanning tree with bottleneck (MBST) algorithm is known as the Camerinis algorithm . It works in linear time and looks like this:

  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. 

In pseudo code:

 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 

Implementation notes:

• The median can be found in O (n) .
• Line 7 can generate a disjoint-set data structure using BFS or DFS.
• Line 13 includes filtering edges in A, where each edge has endpoints that are either in two different connected components in F, or one endpoint is not a vertex in F, and the other is in F, or both are not in F. These tests can be performed using an effective data structure with an unconnected network at O ​​(1) depreciation time for each edge.

Update: now I also created a Wikipedia page on this topic.