kruskal in c++

Kruskal's algorithm is a greedy algorithm used to find the minimum spanning tree (MST) of a graph. Here is an implementation of Kruskal's algorithm in C++:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure to represent an edge in the graph
struct Edge {
    int src, dest, weight;
};

// Structure to represent a disjoint set
struct DisjointSet {
    vector<int> parent, rank;

    // Constructor
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n);

        // Initialize each element as a disjoint set
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // Find the root of a set
    int find(int i) {
        if (i != parent[i]) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    // Union two sets
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
};

// Function to compare edges by weight in non-decreasing order
bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

// Function to find the minimum spanning tree using Kruskal's algorithm
vector<Edge> kruskal(vector<Edge>& edges, int numVertices) {
    // Sort the edges in non-decreasing order of weight
    sort(edges.begin(), edges.end(), compareEdges);

    vector<Edge> mst;
    DisjointSet ds(numVertices);

    // Iterate through all edges in sorted order
    for (const auto& edge : edges) {
        int srcRoot = ds.find(edge.src);
        int destRoot = ds.find(edge.dest);

        // Check if including this edge creates a cycle
        if (srcRoot != destRoot) {
            // Add the edge to the MST
            mst.push_back(edge);

            // Union the two sets
            ds.unionSets(srcRoot, destRoot);
        }
    }

    return mst;
}

int main() {
    int numVertices, numEdges;
    cin >> numVertices >> numEdges;

    vector<Edge> edges(numEdges);

    for (int i = 0; i < numEdges; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    vector<Edge> mst = kruskal(edges, numVertices);

    for (const auto& edge : mst) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
    }

    return 0;
}

Explanation of Kruskal's Algorithm

1. First, we define a structure Edge to represent an edge in the graph. It has three members: src (source vertex), dest (destination vertex), and weight (weight of the edge).
2. Next, we define a structure DisjointSet to represent a disjoint set. It has two vectors: parent (to store the parent of each element) and rank (to store the rank of each element).
3. In the DisjointSet constructor, we initialize each element as a disjoint set, with itself as the parent and rank 0.
4. The find function of the DisjointSet structure is used to find the root of a set using the path compression technique.
5. The unionSets function of the DisjointSet structure is used to union two sets based on their ranks.
6. The compareEdges function is a helper function used to compare two edges by weight in non-decreasing order.
7. The kruskal function takes a vector of edges and the number of vertices as input and returns the minimum spanning tree (MST) of the graph.
8. In the kruskal function, we first sort the edges in non-decreasing order of weight using the sort function and the compareEdges function.
9. We create an empty vector mst to store the edges of the MST.
10. We create an instance of the DisjointSet structure with the number of vertices as input.
11. We iterate through all the edges in sorted order and check if including the edge creates a cycle in the MST.
12. If including the edge does not create a cycle, we add the edge to the MST and union the two sets using the unionSets function.
13. Finally, we return the MST.
14. In the main function, we take input for the number of vertices and edges, and the details of each edge.
15. We call the kruskal function with the input edges and number of vertices, and store the MST in the mst vector.
16. We print the source vertex, destination vertex, and weight of each edge in the MST.