The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Kruskal’s algorithm finds the MST in time O(E log V). It is a greedy algorithm that always tries to add the next least-cost edge to the current set of edges in the MST if its addition does not create a cycle in the MST.
The algorithm can be described as follows:
Checking for cycles can be done with the help of union-find/disjoint set data structure. Initially, each vertex is in its own set. When we are trying to add an edge (u, v) to the MST, we first check if they belong to the same set in which case adding that edge will create a cycle. If they don’t belong to the same set, we add the edge to the MST and merge the sets containing the vertices u and v.
Running time analysis: Sorting takes time O(E log E) and each query to the union-find data structure takes time O(log* V). Since there are E such queries, the overall running time is O(E log E + E log* V) = O(E log E) = O(E log V) (since E is at most V2) i.e., time for sorting dominates the overall running time of the algorithm. If the edges are already sorted, then running time reduces to O(E log* V).
Take a look at the C++ implementation.
Try your hand at problem MST, which uses this idea.