A greedy algorithm that finds an MST by sorting edges and adding them if they don't form a cycle.
Kruskal's algorithm is a classic greedy approach to finding a Minimum Spanning Tree (MST). The algorithm's strategy is simple yet powerful: always add the next cheapest edge that doesn't create a cycle. It operates on the entire graph at once, rather than growing from a single vertex like Prim's algorithm. The process begins by sorting all the edges in the graph by their weight in ascending order. Then, it iterates through this sorted list of edges. For each edge `(u, v)`, it checks if adding this edge to the set of selected edges would form a cycle. If it does not form a cycle, the edge is added to the MST. This continues until `V-1` edges have been added to the MST (where V is the number of vertices), at which point all vertices are connected. The main challenge in implementing Kruskal's is efficiently detecting cycles. This is where the Disjoint Set Union (DSU) data structure becomes indispensable. Using DSU, we can determine in near-constant time if two vertices `u` and `v` are already in the same connected component. The overall time complexity of Kruskal's algorithm is dominated by the edge sorting step, making it O(E log E).