Kruskal’s Algorithm [ Minimum Spanning Tree ]

Kruskal’s Algorithm [ Minimum Spanning Tree ]

গ্রাফ থিওরিতে হাতেখড়ি ৬: মিনিমাম স্প্যানিং ট্রি(ক্রুসকাল অ্যালগোরিদম)

Visualization

Hackerearth

Implementation 01:

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

#include<bits/stdc++.h> using namespace std; const int maxn = (int) 2e5 + 5; struct edge { int u,v,w; }; vector<edge>graph, output; int parent[maxn], mstValue = 0; bool cmp (edge a, edge b) { return a.w < b.w; } int Find(int r) { if(parent[r] == r) return r; return parent[r] = Find(parent[r]); } void initPar(int r) { for(int i = 0; i <= r; i++)parent[i] = i; } void kruskals_Algorithm(int n) { sort(graph.begin(), graph.end(), cmp); for(int i = 0; i < (int)graph.size(); i++){ cout << graph[i].u << " "<<graph[i].v << " "<< graph[i].w<<endl; } initPar(n); int cnt = 0; for(int i = 0; i < (int)graph.size(); i++){ int uPr = Find(graph[i].u); int vPr = Find(graph[i].v); if(uPr != vPr){ if(cnt == n-1) break; output.push_back(graph[i]); mstValue += graph[i].w; parent[uPr] = vPr; cnt++; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); // freopen("in.txt", "r", stdin); int n,e; cin >> n >> e; cout << n << " & " << e << endl; for(int i = 0; i < e; i++){ int u,v,w; cin >> u >> v >> w; edge input; input.u = u; input.v = v; input.w = w; graph.push_back(input); } kruskals_Algorithm(n); cout << "MST Value : " << mstValue << endl; for(int i = 0; i < (int)output.size(); i++){ cout << output[i].u << " "<<output[i].v << " "<< output[i].w<<endl; } return 0; }

Implementation 02:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

#include<bits/stdc++.h> using namespace std; const int MAX = 300005; int id[MAX], nodes, edges, idx; pair <int, pair<int, int> > p[MAX], output[MAX]; void initialize() { for(int i = 0; i < MAX; i++) { id[i] = i; } } int root(int x) { while(id[x] != x) { id[x] = id[ id[x] ]; x = id[x]; } return x; } void union1(int x, int y) { int p = root(x); int q = root(y); id[p] = id[q]; } int kruskal(pair <int, pair<int, int> > p[]) { idx = 0; int x,y; int cost, minimumcost = 0; for(int i = 0; i < edges; i++) { /// selecting edges one by one in increasing order from the beginning. x = p[i].second.first; y = p[i].second.second; cost = p[i].first; /// check if the selected edge is creating a cycle or not if(root(x) != root(y)) { minimumcost += cost; output[idx++] = make_pair(cost, make_pair(x,y)); union1(x,y); } } return minimumcost; } int main() { // freopen("in.txt", "r", stdin); int x,y; int weight,cost,minimumcost,price; initialize(); scanf("%d %d", &nodes, &edges); //cout << nodes << " & "<<edges<<endl; for(int i = 0; i < edges; i++) { cin >> x >> y >> weight; p[i] = make_pair(weight, make_pair(x,y)); } sort(p, p+edges); // for(int i = 0; i < edges; i++){ // cout << p[i].second.first << " "<<p[i].second.second << " "<<p[i].first<<endl; //} minimumcost = kruskal(p); cout << "MST :- "; cout << minimumcost<<endl; for(int i = 0; i < idx; i++){ cout << output[i].second.first << " "<<output[i].second.second << " "<< output[i].first << endl; } return 0; }

Share: