#include "DisjSets.h"

/** * Construct the disjoint sets object. * numElements is the initial number of disjoint sets. */ DisjSets::DisjSets( unsigned numElements ) : s( numElements, -1 ) { }

/** * Union two disjoint sets. * For simplicity, we assume root1 and root2 are distinct * and represent set names. * root1 is the root of set 1. * root2 is the root of set 2. */ void DisjSets::unionSets( int root1, int root2 ) { if( s[ root2 ]

/** * Perform a find. * Error checks omitted again for simplicity. * Return the set containing x. */ int DisjSets::find( int x ) const { if( s[ x ]

/** * Perform a find with path compression. * Error checks omitted again for simplicity. * Return the set containing x. */ int DisjSets::find( int x ) { if( s[ x ]

#ifndef DISJ_SETS_H #define DISJ_SETS_H

// DisjSets class // // CONSTRUCTION: with int representing initial number of sets // // ******************PUBLIC OPERATIONS********************* // void union( root1, root2 ) --> Merge two sets // int find( x ) --> Return set containing x // ******************ERRORS******************************** // No error checking is performed

#include using namespace std;

/** * Disjoint set class. * Use union by rank and path compression. * Elements in the set are numbered starting at 0. */ class DisjSets { public: explicit DisjSets( unsigned numElements );

int find( int x ) const; int find( int x ); void unionSets( int root1, int root2 );

private: vector s; };

#endif

/*

* Driver.cpp

#include

#include

#include

#include "kruskal.h"

#include "Edge.h"

using namespace std;

int main( int argc, char* argv[] ) {

vector edges;

/* works perfectly

Edge e1(2,1,2), e2(1,3,5),e3(4,3,1);

vector spanningTree{e1,e2,e3};

edges.push_back(e1);

edges.push_back(e2);

edges.push_back(e3);

spanningTree=kruskal(edges,4); // 4 -number vertices

*/

//vertices a=0, b=1,c=2,d=3,e=4,f=5

Edge

ab(0,1,4),

ac(0,2,1),

bc(1,2,3),

bd(1,3,6),

be(1,4,5),

bf(1,5,4),

cd(2,3,4),

de(3,4,2),

df(3,5,3),

ef(4,5,2);

// cout

vector spanningTree{ab,ac,bc};

edges.push_back(ab);

edges.push_back(ac);

edges.push_back(bc);

edges.push_back(bd);

edges.push_back(be);

edges.push_back(bf);

edges.push_back(cd);

edges.push_back(de);

edges.push_back(df);

edges.push_back(ef);

cout

for (auto& a: edges)

{

cout

}

cout

spanningTree=kruskal(edges,6); // 6 -number vertices

int sum=0;

for (auto& a: spanningTree)

{

cout

sum+=a.getWeight();

}

cout

return 0;

}

Write a program to implement Kruskal's algorithm. Test the algorithm on the following graph and verify the value of the MST. The output of the algorithm should give the set of vertices with the associated edges and the total weight of the MST 4 5 4 You can find DisiSets.b and DisjiSets.cpp and Driver.cpp in this folder Edge.h, Edge.cpp and kruskal.b implement yourself