এই টিউটোরিয়ালে, আমরা সি++ STL-এ ক্রুস্কালস মিনিমাম স্প্যানিং ট্রি সম্পর্কে আলোচনা করব।
এখানে একটি কানেক্টেড, আনডাইরেক্টেড এবং ওয়েটেড গ্রাফ দেওয়া থাকবে। আমাদের দिये गये গ্রাফের জন্য মিনিমাম স্প্যানিং ট্রি ক্যালকুলেট করতে হবে।
উদাহরণ
#include<bits/stdc++.h> using namespace std; typedef pair<int, int> iPair; // গ্রাফ স্ট্রাকচার struct Graph{ int V, E; vector< pair<int, iPair> > edges; Graph(int V, int E){ this->V = V; this->E = E; } void addEdge(int u, int v, int w){ edges.push_back({w, {u, v}}); } int kruskalMST(); }; struct DisjointSets{ int *parent, *rnk; int n; DisjointSets(int n){ this->n = n; parent = new int[n+1]; rnk = new int[n+1]; for (int i = 0; i <= n; i++){ rnk[i] = 0; parent[i] = i; } } int find(int u){ if (u != parent[u]) parent[u] = find(parent[u]); return parent[u]; } void merge(int x, int y){ x = find(x), y = find(y); if (rnk[x] > rnk[y]) parent[y] = x; else parent[x] = y; if (rnk[x] == rnk[y]) rnk[y]++; } }; int Graph::kruskalMST(){ int mst_wt = 0; sort(edges.begin(), edges.end()); DisjointSets ds(V); vector< pair<int, iPair> >::iterator it; for (it=edges.begin(); it!=edges.end(); it++){ int u = it->second.first; int v = it->second.second; int set_u = ds.find(u); int set_v = ds.find(v); if (set_u != set_v){ cout << u << " - " << v << endl; mst_wt += it->first; ds.merge(set_u, set_v); } } return mst_wt; } int main(){ int V = 9, E = 14; Graph g(V, E); g.addEdge(0, 1, 4); g.addEdge(0, 7, 8); g.addEdge(1, 2, 8); g.addEdge(1, 7, 11); g.addEdge(2, 3, 7); g.addEdge(2, 8, 2); g.addEdge(2, 5, 4); g.addEdge(3, 4, 9); g.addEdge(3, 5, 14); g.addEdge(4, 5, 10); g.addEdge(5, 6, 2); g.addEdge(6, 7, 1); g.addEdge(6, 8, 6); g.addEdge(7, 8, 7); cout << "Edges of MST are \n"; int mst_wt = g.kruskalMST(); cout << "\nWeight of MST is " << mst_wt; return 0; }আউটপুট
Edges of MST are 6 - 7 2 - 8 5 - 6 0 - 1 2 - 5 2 - 3 0 - 7 3 - 4 Weight of MST is 37
