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 $F$, but both its endpoints are in the same component of $F$.
• An edge is safe if it is the minimum-weight edge with exactly one endpoint in some component of $F$.

The same edge could be safe for two different components of $F$. Some edges of $G \backslash F$ are neither safe nor useless; we call these edges undecided.