Kruskal's MST Algorithm

Kruskal's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph. An MST is a subgraph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

The algorithm works as follows:

1. Create a list of all edges in the graph and sort them in non-decreasing order of their weights.
2. Initialize the MST as an empty set.
3. Initialize a Union-Find data structure with each vertex in its own set.
4. Iterate through the sorted edges. For each edge (u, v):
   • If find(u) is not equal to find(v), it means that adding this edge will not form a cycle.
   • Add the edge to the MST and perform a union(u, v).
5. The algorithm terminates when the MST has V - 1 edges, where V is the number of vertices.

Kruskal's algorithm is particularly efficient for sparse graphs (graphs with relatively few edges). Its time complexity is dominated by the edge sorting step, which is O(E log E), where E is the number of edges.