/** * Construct the disjoint sets object. * numElements is the initial number of

Question

/**
* 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 ] < s[ root1 ] ) // root2 is deeper
s[ root1 ] = root2; // Make root2 new root
else
{
if( s[ root1 ] == s[ root2 ] )
--s[ root1 ]; // Update height if same
s[ root2 ] = root1; // Make root1 new root
}
}

/**
* Perform a find.
* Error checks omitted again for simplicity.
* Return the set containing x.
*/
int DisjSets::find( int x ) const
{
if( s[ x ] < 0 )
return x;
else
return find( 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 ] < 0 )
return x;
else
return s[ x ] = find( 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 <vector>
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<int> s;
};

#endif

/*

* Driver.cpp

#include <iostream>

#include <fstream>

#include <vector>

#include "kruskal.h"

#include "Edge.h"

using namespace std;

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

vector<Edge> edges;

/* works perfectly

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

vector<Edge> 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<<"AAA"<<endl;

vector<Edge> 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<<"Graph edges: vertice1, vertice2, weight of the edge "<<endl;

for (auto& a: edges)

{

cout<<"edge:"<<a.getu()<<", "<<a.getv()<<", "<<a.getWeight()<<" ";

}

cout<<"Kruskal spanning tree edges: vertice1, vertice2, weight of the edge"<<endl;

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

int sum=0;

for (auto& a: spanningTree)

{

cout<<"edge:"<<a.getu()<<", "<<a.getv()<<", "<<a.getWeight()<<" ";

sum+=a.getWeight();

}

cout<<"sum = "<<sum<<endl;

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.

Explanation / Answer

Edge.h

#ifndef __EDGE_H__
#define __EDGE_H__

// class to define an edge.
class Edge {
   int u,v,weight;

   public:
   // Constructor with arguments.
   Edge(int s, int t, int w): u(s), v(t), weight(w) {}

   // returns the source of edge.
   int getu();
   // returns the target of edge.
   int getv();
   // returns the weight of edge.
   int getWeight();

};

#endif

Edge.cpp

#include "Edge.h"

// Implementation from edge.h file
int Edge::getu() {
   return u;
}

int Edge::getv() {
   return v;
}

int Edge::getWeight() {
   return weight;
}

kruskal.h

#ifndef __KRUSKAL_H__
#define __KRUSKAL_H__

#include <vector>
#include <algorithm>
#include "Edge.h"
#include "DisjSets.h"

using namespace std;
bool edgeCmp(Edge a, Edge b) {
   //class Edge* a1 = (class Edge*)a;
   //class Edge* b1 = (class Edge*)b;

   return a.getWeight() > b.getWeight();
}

vector<Edge> kruskal(vector<Edge> edges, unsigned nodes) {

   //set of Minimum spanning tree edges
   vector<Edge> mstEdges;

   // sorting the edges compared to their weights.
   sort(edges.begin(), edges.end(), edgeCmp);

   // an object of DisjSets to use the find and union function.
   // it takes the number of nodes in the algorithm
   DisjSets dSets(nodes);

   int cnt = 0;

   // MST has only n-1 edges in it. thus we will find the potential
   // n-1 edges. Hence we iterate for nodes - 1 times.
   while(cnt < nodes - 1) {

      Edge e = edges.back();
      edges.pop_back();

      // find the parent of source of edge
      int x = dSets.find(e.getu());
      // find the parent of target of edge
      int y = dSets.find(e.getv());

      // if the parents are equal then they are already joined.
      // if not then we add the edge in the answer set and do the union.
      if(x!=y){
         mstEdges.push_back(e);
         dSets.unionSets(x,y);
         cnt++;
      }

   }
   return mstEdges;
}
#endif

Sample output:

Graph edges: vertice1, vertice2, weight of the edge
edge:0, 1, 4
edge:0, 2, 1
edge:1, 2, 3
edge:1, 3, 6
edge:1, 4, 5
edge:1, 5, 4
edge:2, 3, 4
edge:3, 4, 2
edge:3, 5, 3
edge:4, 5, 2
Kruskal spanning tree edges: vertice1, vertice2, weight of the edge
edge:0, 2, 1
edge:4, 5, 2
edge:3, 4, 2
edge:1, 2, 3
edge:2, 3, 4
sum = 12

Rest all files are untouced.

Thanks,

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.