Lecture 379:- Kruskal's Minimum Cost Spanning Tree

Kruskal's algorithm is another greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected graph with weighted edges. The main idea behind Kruskal's algorithm is to repeatedly add the shortest edge that does not form a cycle in the current MST.

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. Initialize an empty MST and a disjoint set data structure to keep track of connected components.
3. Start adding edges to the MST in non-decreasing order of weights.
   • If adding the edge does not form a cycle in the current MST (i.e., the two vertices of the edge are not in the same connected component), then add the edge to the MST.
   • If adding the edge forms a cycle, skip it and move to the next edge.
4. Continue this process until all vertices are included in the MST.

Here's a C++ implementation of Kruskal's algorithm:

cppCopy code

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Edge {    int src, dest, weight; }; // Comparator function for sorting edges based on weights in non-decreasing order bool compareEdges(const Edge& edge1, const Edge& edge2) {    return edge1.weight < edge2.weight; } class DisjointSet { public:    vector<int> parent, rank;    DisjointSet(int size) {        parent.resize(size);        rank.resize(size, 0);        for (int i = 0; i < size; ++i) {            parent[i] = i;        }    }    int find(int x) {        if (parent[x] != x) {            parent[x] = find(parent[x]);        }        return parent[x];    }    void unionSets(int x, int y) {        int rootX = find(x);        int rootY = find(y);        if (rootX != rootY) {            if (rank[rootX] > rank[rootY]) {                parent[rootY] = rootX;            } else if (rank[rootX] < rank[rootY]) {                parent[rootX] = rootY;            } else {                parent[rootY] = rootX;                rank[rootX]++;            }        }    } }; // Function to find the minimum cost spanning tree using Kruskal's algorithm vector<Edge> kruskalMST(vector<Edge>& edges, int vertices) {    // Sort the edges in non-decreasing order of weights    sort(edges.begin(), edges.end(), compareEdges);    DisjointSet ds(vertices);    vector<Edge> mst;    for (Edge& edge : edges) {        int srcParent = ds.find(edge.src);        int destParent = ds.find(edge.dest);        // Add the edge to the MST if it does not form a cycle        if (srcParent != destParent) {            mst.push_back(edge);            ds.unionSets(srcParent, destParent);        }    }    return mst; } int main() {    int vertices, edges;    cout << "Enter the number of vertices and edges: ";    cin >> vertices >> edges;    vector<Edge> graph(edges);    cout << "Enter the edges (source, destination, weight):" << endl;    for (int i = 0; i < edges; ++i) {        cin >> graph[i].src >> graph[i].dest >> graph[i].weight;    }    vector<Edge> mst = kruskalMST(graph, vertices);    // Print the MST    cout << "Minimum Spanning Tree using Kruskal's Algorithm:\n";    for (Edge& edge : mst) {        cout << "Edge: " << edge.src << " - " << edge.dest << " Weight: " << edge.weight << endl;    }    return 0; }

In this implementation, the graph is represented as a vector of edges, where each edge contains the source vertex, destination vertex, and weight. The kruskalMST function performs Kruskal's algorithm to find the MST. The MST is represented as a vector of edges. The algorithm uses a disjoint set data structure to efficiently check if adding an edge forms a cycle in the current MST.