### Kruskal's Minimum Spanning Tree

Hi, can somebody help me implement Kruskal's Minimum Spanning Tree algorithm? I have Prim's algorithm completed already. I'm not sure how the MST works. Any advice or solutions would be greatly appreciated.

Thanks!

MAIN FILE
 ``12345678910111213141516171819202122232425262728293031323334353637`` ``````// File PrimMain.cpp // Build together with Prim.h and Prim.cpp #include "Prim.h" void getFigure9_2(vector > & alist); int main(void){ vector > adjList; string answer; cout << "Use default graph? (Y/N): "; cin >> answer; if (answer == "Y" || answer== "y"){ getFigure9_2(adjList); int tw = PrimsAlg(adjList); cout << "The sum of the edge weights in the MST is " << tw << endl; } else { cout << "TODO: implement reading the adjacency list from a file\n"; return 1; } } void getFigure9_2(vector > & alist){ alist.resize(6); // have 6 vertices int i,j,w; int data[6][6] = { {0,3,0,0,6,5}, {3,0,1,0,0,4}, {0,1,0,6,0,4}, {0,0,6,0,8,5}, {6,0,0,8,0,2}, {5,4,4,5,2,0}}; for (i = 0; i < 6; i++) for (j = 0; j < 6; j++) if (w = data[i][j]) alist[i].push_back(destV(char(j+'a'),w)); }``````

PRIM'S ALGORITHM
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879`` ``````#include "Prim.h" ostream& operator<<(ostream & o, const vinfo &vi){ o << vi.name << "(" << vi.nearv << ","; if (vi.dist == INF) o << "INF"; else o << vi.dist; o << ")"; return o; } bool vinfo_less(const vinfo & vi1, const vinfo &vi2){ return (vi1.dist > vi2.dist); } void printVertices(vector & VR){ for (vector::iterator vit = VR.begin(); vit != VR.end(); vit++) cout << *vit << ", "; cout << endl; } int PrimsAlg(const vector > & alist){ vector VT,Vremaining; int i,edgeweight,n = alist.size(), totalWeight = 0; vector VinTree(n,false); vinfo next; char vertex,ustar; destV temp; list::const_iterator it; // Initialize set of tree vertices with the first vertex in the adjacency list vertex = 'a'; VinTree[0] = true; next = vinfo(vertex,'-',0); //VT.push_back(vinfo(vertex,'-',0)); VT.push_back(next); // “Remaining edges” are either adjacent to the first vertex, // or not adjacent to the first vertex for (it = alist[0].begin(); it != alist[0].end(); it++) Vremaining.push_back(vinfo(it->name,vertex,it->weight)); for (i = 1; i < n; i++){ // The ones that are not adjacent temp = destV(char('a'+i),0); if (find(alist[0].begin(),alist[0].end(),temp)==alist[0].end()) Vremaining.push_back(vinfo(char('a'+i),'-',INF)); } make_heap(Vremaining.begin(),Vremaining.end(),vinfo_less); cout << "Start: " << next << ", Remaining vertices: "; printVertices(Vremaining); // here is the main loop for (i = 1; i < n; i++){ next = Vremaining.front(); pop_heap (Vremaining.begin(),Vremaining.end(),vinfo_less); Vremaining.pop_back(); VT.push_back(next); ustar = next.name; VinTree[ustar-'a'] = true; const list &vneighbors = alist[ustar-'a']; bool updatedPriorityQueue = false; for (it = vneighbors.begin(); it != vneighbors.end(); it++) if (!VinTree[(it->name)-'a']){ edgeweight = it->weight; vector::iterator loc = find(Vremaining.begin(), Vremaining.end(),vinfo(it->name)); if (loc != Vremaining.end() && loc->dist > edgeweight){ loc->nearv = ustar; loc->dist = edgeweight; updatedPriorityQueue = true; } } if (updatedPriorityQueue) make_heap(Vremaining.begin(),Vremaining.end(),vinfo_less); cout << "Next: " << next << ", Remaining vertices: "; printVertices(Vremaining); } // totalWeight has been initialized to 0 for (vector::iterator VTit = VT.begin(); VTit != VT.end(); VTit++) totalWeight += VTit->dist; return totalWeight; }``````

 ``1234567891011121314151617181920212223242526272829303132333435363738`` ``````#include #include #include #include #include using namespace std; const int INF = INT_MAX; // a node in the adjacency list struct destV{ char name; int weight; destV(char n = '-', int w=0):name(n),weight(w){} bool operator==(const destV &other) const { return (name == other.name); } }; // a node in list of "remaining vertices" for the algorithm execution class vinfo{ private: char name; char nearv; // name of the nearest tree vertex int dist; // weight of the corresponding edge public: vinfo(char v1='-', char v2 = '-', int d = INF): name(v1),nearv(v2),dist(d){} bool operator==(const vinfo & other) const{ return name == other.name; } friend ostream& operator<<(ostream & o, const vinfo &vi); friend int PrimsAlg(const vector > & alist); friend bool vinfo_less(const vinfo & vi1, const vinfo &vi2); }; extern int PrimsAlg(const vector > & alist);``````
You mentioned that you have trouble understanding how minimum spanning trees "work". Are you familiar with the concept of a minimum spanning tree or are you having trouble understanding Kruskal's algorithm for finding one?

-Albatross
Minimum spanning trees are just connected subgraphs that are trees.

Kruskal's algorithm basically askes you to create an identical graph T to the original graph G. "T" only has vertices from "G", but none of the edges. You take all the edges from "G" and put it into a set/list. Then you order that list or set from lowest to highest. You keep adding the least weight edges from the set to "T" (while eliminating the edge from the set) while making sure it doesn't make "T" have cycles/circuit (depending on what book you used, the terminology can be different). Eventually you'll get a minimum spanning tree.

If you're asking us to "implement" an algorithm for you, you're sorely mistaken. You have to do your own homework.
Last edited on
Topic archived. No new replies allowed.