c++ kruskal algorithm

Kruskal's Algorithm in C++

Kruskal's algorithm is a minimum-spanning-tree algorithm that finds an undirected graph's minimum spanning tree. The steps of the algorithm are as follows:

1. Sort the edges by weight: Sort all the edges in non-decreasing order of their weight.

2. Initialize the minimum spanning tree: Create a new graph with the same vertices as the original graph but with no edges.

3. Iterate through the sorted edges: For each edge in the sorted list, starting from the smallest, check if adding the current edge to the minimum spanning tree forms a cycle. If not, add the edge to the minimum spanning tree.

4. Check for cycles using Union-Find: To check for cycles, use the Union-Find algorithm. If the current edge connects two vertices that are already in the same set, adding this edge will create a cycle. If not, the edge can be added to the minimum spanning tree.

5. Repeat until all vertices are connected or V-1 edges are added: Continue adding edges to the minimum spanning tree until all the vertices are connected or V-1 edges have been added, where V is the number of vertices in the original graph.

The C++ implementation of Kruskal's algorithm involves using a disjoint-set data structure to efficiently determine whether adding an edge creates a cycle and to merge sets of vertices. The algorithm's time complexity is O(E log E), where E is the number of edges in the graph.