Skip to content
Tutorials Center
My learning

Topics

Lesson 140 of 225 ยท Shortest Paths and Spanning Trees

Boruvka's Algorithm and MST Variants

Learn Boruvka third MST algorithm in Python, then solve MST variants: the minimum bottleneck path, the second-best spanning tree and the maximum spanning tree.

The minimum spanning tree lesson taught Kruskal's and Prim's algorithms. There is a third classic, Boruvka's algorithm, which is the oldest (1926) and the easiest to run in parallel: every component picks its cheapest outgoing edge at the same time, and all those edges are merged in one round. The number of components at least halves each round, so there are at most log2(V) rounds.

Once you hold an MST, a family of variants becomes easy: the best route where you minimize the worst edge (the minimum bottleneck path), the second-best spanning tree, and the maximum spanning tree. Each follows from one property of MSTs, and we verify each against brute force.

Boruvka's algorithm

Start with every vertex as its own component. Repeat:

  1. For each component, find the cheapest edge leaving it.
  2. Add all those edges to the MST and merge the components they join.

Stop when one component remains. The cheapest edge leaving any component always belongs to some MST (the cut property), so each added edge is safe. If edge weights tie, break ties consistently (for example by edge index); otherwise two components might pick different edges of equal weight that together form a cycle.

flowchart TD
  A["Each vertex = its own component"] --> B["For every component, find the cheapest outgoing edge"]
  B --> C["Add all chosen edges, merge components"]
  C --> D{"One component left?"}
  D -->|no| B
  D -->|yes| E["Done: MST"]

Every round at least halves the number of components, so there are at most log2(V) rounds.

Each round scans all E edges once with a union-find structure (union-find), so the time is O(E log V), the same as Kruskal but without sorting.

Python Boruvka's algorithm with a tie-break

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sample graph is solved in a single round, because every component happens to pick an edge of the final tree. The code also handles a disconnected graph: it ends with a spanning forest when no component has an outgoing edge.

Minimum bottleneck path

In a weighted graph, the bottleneck of a path is its heaviest edge. The minimum bottleneck path between s and t minimizes that heaviest edge. Think of the smallest cable capacity you must have so that s can reach t using only cables of weight at most x.

Fact: the path between s and t inside the MST is a minimum bottleneck path. Reason: if a path used smaller maximum weight than the tree path, you could swap an edge in the MST for a cheaper one and get a lighter tree, contradicting minimality.

So: build the MST once, then each query is "largest edge on the tree path", answered by a DFS in O(V), or faster with binary lifting from binary lifting and LCA.

Python Bottleneck queries via the MST

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Second-best MST

The second-best MST is the lightest spanning tree that is not equal to the MST (it may have the same weight when ties exist). Fact: it differs from the best MST by exactly one swap: add one non-tree edge (u, v, w) and remove the heaviest edge on the tree path between u and v. Try every non-tree edge, and take the cheapest result:

TEXT
candidate weight = MST weight + w - max edge on tree path(u, v)

With the path maximum computed in O(V) per edge by a DFS, the whole algorithm is O(E * V) on small graphs, or O(E log V) with binary lifting.

Python Second-best MST by one swap, checked by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force enumerates every set of n - 1 edges and keeps the valid trees, then reads off the second smallest total. It agrees with the swap-based method, which confirms the one-swap fact.

Maximum spanning tree

To get the heaviest spanning tree, negate the weights, or simply sort in descending order in Kruskal. Everything above flips accordingly: the path between two vertices in the maximum spanning tree maximizes the minimum edge (the widest path or maximum-capacity route).

Choosing the algorithm

Situation Choice
Edge list, easy code Kruskal, O(E log E)
Dense graph or adjacency matrix Prim, O(V^2) or O(E log V) with a heap
Parallel or distributed setting, no sorting wanted Boruvka, O(E log V)
Minimize the heaviest edge on a route MST path, or binary search plus union-find
Second-best or constrained trees MST plus one edge swap

Common mistakes: forgetting a consistent tie-break in Boruvka (cycles appear), ignoring self-loops in the second-best search, and assuming the second-best tree always has a strictly larger weight (with equal weights the answer may equal the MST weight).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many rounds does Boruvka's algorithm need at most on V vertices?

    Every component merges with at least one other each round, so the number of components at least halves.
  2. 2. Why does Boruvka need a consistent tie-break among equal-weight edges?

    With equal weights, components could choose different edges that form a cycle. Comparing (weight, index) makes the choice unambiguous.
  3. 3. Which path in the graph is a minimum bottleneck path between s and t?

    If a path had a smaller maximum edge than the tree path, swapping edges would produce a lighter spanning tree, a contradiction.
  4. 4. How is the second-best MST obtained from the best MST?

    The second-best tree differs from the best by one edge swap. Each candidate costs MST weight + w - max path edge.

Summary

  • Boruvka's algorithm lets every component pick its cheapest outgoing edge and merges them all each round: at most log2(V) rounds, O(E log V) total.
  • Use a deterministic tie-break such as (weight, index).
  • The tree path between two vertices in an MST is a minimum bottleneck path.
  • The second-best MST is one swap away: add a non-tree edge, remove the maximum edge on the resulting cycle.
  • A maximum spanning tree comes from sorting edges in descending order.

Next: Strongly Connected Components