PHD Discussions Logo

Ask, Learn and Accelerate in your PhD Research

Question Icon Post Your Answer

Question Icon

7 years ago in Algorithms By Prajwal Sharma

Implementing Kruskal algorithm in C++

How to implement Kruskal algorithm in C++? Please provide me the codes.

All Answers (4 Answers In All)

By Nadeemimi Answered 7 years ago

#include #include #include using namespace std; #define edge pair class Graph { private: vector G; // graph vector T; // mst int *parent; int V; // number of vertices/nodes in graph public: Graph(int V); void AddWeightedEdge(int u, int v, int w); int find_set(int i); void union_set(int u, int v); void kruskal(); void print(); }; Graph::Graph(int V) { parent = new int[V]; //i 0 1 2 3 4 5 //parent[i] 0 1 2 3 4 5 for (int i = 0; i < V; i++) parent[i] = i; G.clear(); T.clear(); } void Graph::AddWeightedEdge(int u, int v, int w) { G.push_back(make_pair(w, edge(u, v))); } int Graph::find_set(int i) { // If i is the parent of itself if (i == parent[i]) return i; else // Else if i is not the parent of itself // Then i is not the representative of his set, // so we recursively call Find on its parent return find_set(parent[i]); } void Graph::union_set(int u, int v) { parent[u] = parent[v]; } void Graph::kruskal() { int i, uRep, vRep; sort(G.begin(), G.end()); // increasing weight for (i = 0; i < G.size(); i++) { uRep = find_set(G[i].second.first); vRep = find_set(G[i].second.second); if (uRep != vRep) { T.push_back(G[i]); // add to tree union_set(uRep, vRep); } } } void Graph::print() { cout

By Renu Answered 7 years ago

Do you want to generate Minimum Cost Spanning Tree Kruskal algorithm?

By Prajwal Sharma Answered 7 years ago

Yes mam! I want to implement kruskal algorithm to generate Minimum Cost Spanning Tree. Any suggestions?

By Renu Answered 7 years ago

Use the below codes for the implementation of Kruskal algorithm. #include #include #include using namespace std; int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p; main() { int dup1,dup2; cout n; cout m; cout >j >>c; cost[i][j]=c; cost[j][i]=c; } for(i=1;i

Your Answer