Program 1:
Design and implement C/C++ Program to find Minimum Cost Spanning Tree of a given
connected undirected graph using Kruskal's algorithm.
Sol:
A minimum spanning tree (MST) or minimum weight spanning tree for a weighted,
connected, undirected graph is a spanning tree with a weight less than or equal to the weight
of every other spanning tree.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> parent, dsRank;
// Find function with path compression
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
// Union function with rank optimization
void unionSets(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
if (dsRank[rootX] > dsRank[rootY]) parent[rootY] = rootX;
else if (dsRank[rootX] < dsRank[rootY]) parent[rootX] = rootY;
else {
parent[rootY] = rootX;
dsRank[rootX]++;
}
}
}
int kruskal(int n, vector<vector<int>>& edges) {
sort(edges.begin(), edges.end(), [](vector<int>& a, vector<int>& b) {
return a[2] < b[2]; // Sort by weight
});
parent.resize(n);
dsRank.assign(n, 0); // Use dsRank instead of rank
for (int i = 0; i < n; i++) parent[i] = i;
int mstWeight = 0, edgesUsed = 0;
for (auto& e : edges) {
int u = e[0], v = e[1], weight = e[2];
if (find(u) != find(v)) {
unionSets(u, v);
mstWeight += weight;
edgesUsed++;
if (edgesUsed == n - 1) break; // Stop when MST is formed
}
}
return mstWeight;
}
int main() {
int n = 4; // Number of nodes
vector<vector<int>> edges = {
{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}
};
cout << "Minimum Cost of Spanning Tree: " << kruskal(n, edges) << endl;
return 0;
}
