What is the Kruskal's algorithm for finding the Minimum Spanning Tree?

What is the Kruskal's algorithm for finding the Minimum Spanning Tree?

Kruskal's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph. The steps of Kruskal's algorithm are as follows:

1. Sort all the edges of the graph in non-decreasing order of their weights.
2. Create an empty set called the MST.
3. Iterate through the sorted edges, starting from the smallest weight.
4. For each edge, check if adding it to the MST creates a cycle. If not, add the edge to the MST.
5. Continue this process until all the vertices are included in the MST or there are no more edges left.
6. The resulting MST will be the minimum spanning tree of the given graph.

In summary, Kruskal's algorithm selects the edges in ascending order of their weights, adding them to the MST as long as they do not create a cycle. This process ensures that the MST has the minimum total weight among all possible spanning trees of the graph.