Introduction to Minimum Spanning Trees

A minimum spanning tree (MST) of a graph \(G=(V, E)\) with the vertex set \(V\) is a tree \(T=(V, E_T)\) seen as a subset \(E_T\subseteq E\) of the edges \(E\subseteq V\times V\) of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimal possible total edge weight \(c:E\to\mathbb{R}\):

\[c(T) = \sum\limits_{e\in E_T} c(e)\text{, minimal}\]

Tarjan's Algorithm

The basic idea of Tarjan's algorithm is coloring edges either green or red. The edges within the MST become green and the rest become red. To describe the algorithm, a cut of a graph and a cycle of a graph need to be defined first.

Graph Cut

The cut of a graph \(G=(V, E)\) is a vertex partition \((S, V- S)\). Visually it is a cut right through the graph, so that an edge \((v, w)\) crosses the cut \((S, V- S)\) if \(v\in S\) and \(w\in V- S\) or the other way round.

Cycles in a Graph

A cycle within graph \(G\) is a path \(v_1, v_2, ..., v_k\) with \(v_1=v_k, k\geq 3\) and \(v_i, v_{i+1}\in E\).

Green Rule

1. Perform a cut on graph \(G\), that crosses no green edge.
2. From the not yet colored edges take the one with least weight and make it green.

Red Rule

1. Find a cycle in graph \(G\), which contains no red edges.
2. From the not yet colored edges take the one with highest weight and make it red.

Tarjan's algorithm is the iterative application of either the red or the green rule; the order in which the two rules are applied does not matter. The correctness of Tarjan's algorithm, meaning that it always constructs an MST of \(G\) that contains only green and no red edges, can be shown by induction over the invariant that the graph of uncolored and green edges always still contains an MST:

Iteration \(0\): the graph contains an MST, since all edges are uncolored. Iteration \(t\to t+1\):

• Case 1, Red Rule: taking a cycle with no red edges and coloring its heaviest uncolored edge red is safe, because every spanning tree omits at least one edge of that cycle, and the heaviest edge is never the unique cheapest choice for closing it, so it is not needed in any MST.
• Case 2, Green Rule: taking a cut with no green edge and coloring its lightest uncolored edge green is safe, because the two sides of the cut must be joined by some edge in any spanning tree, and the lightest edge crossing the cut can always be used for that purpose without increasing the total weight.

Tarjan's algorithm is a conceptual generalization. Kruskal's and Prim's algorithm are typical algorithms used to tackle the MST problem in practice, and both can be seen as Tarjan's algorithm restricted to only the green rule, since finding cycles directly is comparatively expensive.

Kruskal's Algorithm

1. Sort edges in non-decreasing order, such that \(c(e_1)\leq c(e_2)\leq\dots\leq c(e_m)\).
2. Walk through the sorted edges and add edge \(e_i\) to tree \(T\) if no cycle emerges.

Kruskal's algorithm can be seen as a repeated application of the red rule. In practice, Kruskal's algorithm has the drawback that its edges must be sorted first, which costs \(O(|E|\log|E|)\).

Prim's Algorithm

1. Choose an arbitrary starting vertex \(v_0\).
2. Repeat until all vertices of \(G\) are vertices of \(T\)
   • Take the cheapest edge \(e\in E\) from an already visited vertex \(v\in T\) to a not yet visited vertex \(w\notin T\)
   • Add this edge \(e\) and the newly accessible vertex \(w\) to tree \(T\).

Prim's algorithm can be seen as a repeated application of the green rule. In practice, Prim's algorithm has the problem of quickly finding the cheapest edge leaving the tree, for which a Fibonacci heap gives the best known running time.

Reverse-Delete Algorithm

The reverse-delete algorithm builds an MST as a repeated application of the red rule alone, processing edges in the opposite order of Kruskal's algorithm:

1. Sort edges in non-increasing order, such that \(c(e_1)\geq c(e_2)\geq\dots\geq c(e_m)\).
2. Walk through the sorted edges and remove edge \(e_i\) from \(G\), unless removing it would disconnect the graph.

Since deciding whether an edge is safe to remove requires a connectivity check, for example a breadth-first or depth-first search taking \(O(|V|+|E|)\), a straightforward implementation runs in \(O(|E|(|V|+|E|))\), which is slower in practice than Kruskal's or Prim's algorithm. Its value lies mostly in illustrating the red rule directly, as the counterpart to how Kruskal's algorithm illustrates the green rule.

Worked Example

Consider the following weighted graph on six vertices, with the minimum spanning tree highlighted by thicker edges:

Kruskal's algorithm processes the nine edges in non-decreasing order of weight, accepting an edge unless it closes a cycle:

The five accepted edges, B–C, A–C, D–E, E–F and B–D, already connect all six vertices, giving a total weight of \(1+2+2+3+5=13\). Running Prim's algorithm from vertex \(A\) grows the same tree one cheapest boundary edge at a time, \(A\text{–}C\), \(B\text{–}C\), \(B\text{–}D\), \(D\text{–}E\), \(E\text{–}F\), arriving at the identical set of edges.

The reverse-delete algorithm confirms it from the other direction, walking the same nine edges from heaviest to lightest and removing each one unless it is a bridge. C–E, C–D and D–F are removed without disconnecting the graph; B–D, however, is the only connection between \(\{A,B,C\}\) and \(\{D,E,F\}\) once C–D and D–F are gone, so it stays. A–B is then removed since A–C and B–C still connect \(A\), leaving exactly the five edges B–C, A–C, B–D, D–E and E–F, the same minimum spanning tree found above.

References

• Tarjan1983R. E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.
• Kruskal1956J. B. Kruskal, "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem," Proceedings of the American Mathematical Society, 1956.
• Jarnik1930V. Jarník, "O jistém problému minimálním," Práce Moravské Přírodovědecké Společnosti, 1930.
• Prim1957R. C. Prim, "Shortest Connection Networks and Some Generalizations," Bell System Technical Journal, 1957.