Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 23

The authors discuss minimum-spanning tree (MST) in this chapter along with two greedy algorithms to find minimum spanning tree. The problem is defined as below:
For a connected, undirected graph , there is a cost associated for each edge . Find an acyclic subset that connects all the vertices and whose total weight is minimized.

The authors first provide a generic MST algorithm and discuss its loop invariant. The authors also define following:

• a cut which is a partition of for an undirected graph
• an edge crosses the cut if one of its endpoints is in and the other in .
• a cut respects a set of edges if no edge in crosses the cut
• an edge is called a light edge satisfying a given property if its weight is the minimum satisfying that property
• an edge that does not violate the loop invariant is called safe edge.

The authors then prove a theorem which helps in choosing a safe edge. The authors use this theorem in providing algorithms of Kruskal and Prim and prove their running time to be and respectively.