The Only Minimum Spanning Tree Algorithm

Understand the algorithm and its applications in problem-solving.

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 FF of the input graph GG, which we will call the intermediate spanning forest. At all times, FF satisfies the following invariant:

FF is a subgraph of the minimum spanning tree of GG.

Initially, FF consists of VV one-vertex trees. The generic algorithm connects trees in FF by adding certain edges between them. When the algorithm halts, FF consists of a single spanning tree; our invariant implies that this must be the minimum spanning tree of GG. 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 FF induces two special types of edges in the rest of the graph:

  • An edge is useless if it is not an edge of FF, but both its endpoints are in the same component of FF.
  • An edge is safe if it is the minimum-weight edge with exactly one endpoint in some component of FF.

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

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy