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 $ G = (V,E) $, there is a cost $ w(u,v) $ associated for each edge $ (u,v) \in E $. Find an acyclic subset $ T \subseteq E $ that connects all the vertices and whose total weight $ \displaystyle\sum\limits_{(u,v) \in T}w(u,v) $ is minimized.

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

• a cut $ (S, V-S) $ which is a partition of $V$ for an undirected graph $ G(V, S) $
• an edge $ (u,v) \in E $ crosses the cut $ (S, V-S) $ if one of its endpoints is in $S$ and the other in $ V-S $.
• a cut respects a set $A$ of edges if no edge in $A$ 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 $ (u, v) $ 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 $ O(E \lg V) $ and $O(E + V \lg V)$ respectively.