Explain Kruskal's Algorithm for Minimum Spanning Tree

Question: Explain Kruskal's algorithm for finding the Minimum Spanning Tree (MST) of a graph, and describe how you would implement it in code.

Answer framing: Kruskal's algorithm builds an MST by greedily adding edges in increasing order of weight, skipping any edge that would create a cycle, until the tree has (V-1) edges. Implementation: sort all edges by weight; use a Union-Find (Disjoint Set Union) data structure to efficiently check whether adding an edge would connect two already-connected components (cycle) - for each edge in sorted order, if the two endpoints are in different sets, union them and add the edge to the MST; otherwise skip it. Time complexity O(E log E) for sorting plus near-O(E) for the union-find operations (with path compression and union by rank).