Borůvka's MST

O(E log V)

Borůvka's algorithm — the oldest MST algorithm — works in rounds. Every vertex starts as its own component. In each round, every component simultaneously picks the cheapest edge leaving it, and all those edges are added at once, merging the components they join. Because each round at least halves the number of components, only O(log V) rounds are needed, for O(E log V) overall. Adding many edges in parallel makes it a natural fit for distributed and parallel MST computation, unlike the strictly sequential Prim and Kruskal. Here edge weights are the distances between nodes.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Start with every vertex as its own component.
  2. Each round, every component finds its cheapest outgoing edge.
  3. Add all those edges at once, merging the components they connect (skip duplicates).
  4. Repeat until a single component spans the whole graph.

Pseudocode

1boruvka(graph):                     # O(E log V)2  each vertex starts as its own component3  while more than one component:4    for each component:5      find its cheapest outgoing edge6    add all those edges at once (skip duplicates)7    union the components they join