23. Minimum Spanning Trees 1

G is a connected, weighted, undirected graph G = (V , E ; w).

The Minimum Spanning Tree problem (MST) in G is to find a spanning tree T = (V,E‘) such that the weighted sum of the edges in T is minimised.
(spanning tree is a tree in G with all the vertices in.)

Clearly, if |V| = n, then |E'| = n - 1.

There are two well-known MST algorithms:
1.Kruskal’s algorithm.
2.Prim’s algorithm.

Generic Algorithm for MSTs

The idea is to always maintain the following condition:
INVARIANT: Some minimum spanning tree of G contains A.

If INVARIANT is still true when A has become a spanning tree, then the tree must be a minimum spanning tree in the graph.

Now, We have a set of edges, A, which is empty initially.

The algorithm adopts the greedy strategy: Find tree edges one by one iteratively until the MST is formed. Within each iteration, we add a new edge to A until it finally is a tree spanning all nodes in the graph.

A general strategy for choosing edges so that INVARIANT remains true uses cuts.

1. A cut is a pair (S,V\S),whereS belongs to V.
2. An edge of G crosses the cut (S,V \S) if one endpoint of the edge is in S and the other endpoint of the edge is in V \ S.
3. An edge of G is light for the cut (S,V \S) if it crosses the cut and no other edge crossing the cut has lower weight.

Note: Choosing an edge A belongs to E at each step of an algorithm according to this theorem is a greedy strategy as that edge is a light edge.

Kruskal's algorithm

In Kruskal’s algorithm, the edge added to A at each step is:
an edge a with least weight that does not create a cycle with the edges in A.

The difficult part is to ensure that we do not create a cycle when adding an edge into A.
For this purpose, we keep track of the connected components of G, and only consider edges connecting different connected components.

To maintain different connected components ( or disjoint vertex sets), we make use of the data structures for disjoint set representations, such data structures include linked lists and the forest of inverted trees.

The running time of Kruskal’s algorithm:

1. Sorting the edges according to weight takes time O(|E|log|E|) = O(|E|log|V|). Here, we use the fact that |E| < |V|^2, which implies log|E| < 2log|V|.

2. If we use different data structures to represent disjoint sets and adopt both the “union by rank” and “path compression” heuristics, the time spent on all the Find Set, Make Set, and Union operations in total for the MST construction is O(|E|log|V|).

3. So, the total amount of running time of Kruskal’s is O(|E|log|V|).

Kruskal’s algorithm proceeds iteratively. Within each iteration, it chooses a light edge, so it is a greedy algorithm.