kruskalalg.cpp

#include <iostream>

using namespace std;

class Edge {
public:
    int src, dest, weight;
};

class DisjointSet {
    int *parent, *rank;
public:
    DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    int find(int u) {
        if (parent[u] != u) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void unionSets(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }

    ~DisjointSet() {
        delete[] parent;
        delete[] rank;
    }
};

void sortEdges(Edge *edges, int e) {
    for (int i = 0; i < e - 1; i++) {
        for (int j = 0; j < e - i - 1; j++) {
            if (edges[j].weight > edges[j + 1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
}

void kruskalMST(int n, int e, Edge *edges) {
    sortEdges(edges, e);
    DisjointSet ds(n);

    int mstWeight = 0;
    int edgeCount = 0;

    for (int i = 0; i < e && edgeCount < n - 1; i++) {
        int u = edges[i].src;
        int v = edges[i].dest;
        int w = edges[i].weight;

        if (ds.find(u) != ds.find(v)) {
            ds.unionSets(u, v);
            cout << "Edge: " << u << " - " << v << " Weight: " << w << endl;
            mstWeight += w;
            edgeCount++;
        }
    }

    cout << "Total MST Weight: " << mstWeight << endl;
}

int main() {
    int n, e;
    cout << "Enter number of vertices and edges: ";
    cin >> n >> e;

    Edge *edges = new Edge[e];

    cout << "Enter edges (src dest weight):" << endl;
    for (int i = 0; i < e; i++) {
        cin >> edges[i].src >> edges[i].dest >> edges[i].weight;
    }

    cout << "Minimum Spanning Tree (Kruskal's Algorithm):" << endl;
    kruskalMST(n, e, edges);

    delete[] edges;
    return 0;
}