The Only Minimum Spanning Tree Algorithm

Generic strategy for computing minimum spanning trees

There are many algorithms to compute minimum spanning trees, but almost all of them are instances of the following generic strategy. The situation is similar to graph traversal, where several different algorithms are all variants of the generic traversal algorithm whatever-first search.

The generic minimum spanning tree algorithm maintains an acyclic subgraph $F$ of the input graph $G$, which we will call the intermediate spanning forest. At all times, $F$ satisfies the following invariant:

$F$ is a subgraph of the minimum spanning tree of $G$.

Initially, $F$ consists of $V$ one-vertex trees. The generic algorithm connects trees in $F$ by adding certain edges between them. When the algorithm halts, $F$ consists of a single spanning tree; our invariant implies that this must be the minimum spanning tree of $G$. Obviously, we have to be careful about which edges we add to the evolving forest because not every edge is in the minimum spanning tree.

At any stage of its evolution, the intermediate spanning forest $F$ induces two special types of edges in the rest of the graph:

• An edge is useless if it is not an edge of $$

...