Please implement Kruskal's algorithms by C++ code.
Graph rules :
The graph is an undirected graph, containing at most 10 nodes named 0 ~ 9.
There is just one edge between two nodes.
The weight of all edges is under 100.
Fill in the blanks marked "//TODO"
Template:
// C++ program for Kruskal's algorithm to find Minimum
// Spanning Tree of a given connected, undirected and
// weighted graph
#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;
// Creating shortcut for an integer pair
typedef pair<int, int> iPair;
// Structure to represent a graph
class Graph
{
int V, E;
vector< pair<int, iPair> > edges;
public:
// Constructor
Graph(int V, int E)
{
this->V = V;
this->E = E;
}
// Utility function to add an edge
void addEdge(int u, int v, int w)
{
edges.push_back({w, {u, v}});
}
// Function to find MST using Kruskal's
// MST algorithm
int kruskalMST();
};
// To represent Disjoint Sets
class DisjointSets
{
//Array used to indicate the parent and rank,size or height of each vertex
int *parent, *rnkorsize;
int n;
friend Graph;
// Constructor.
//n is the number of vertices in the graph given by the user
DisjointSets(int n)
{
// Allocate memory
//TODO
// Initially, all vertices are in
// different sets and have rank 0.
//TODO
}
// Find the parent of a node 'u'
// Path Compression
int find(int u)
{
/* Make the parent of the nodes in the path
from u--> parent[u] point to parent[u] */
//TODO
}
// Union by rank,size or height
void merge(int x, int y)
{
//TODO
}
};
/* Functions returns weight of the MST*/
int Graph::kruskalMST()
{
//TODO
}
// Driver program to test above functions
int main()
{
string cmd;
int V ;
int E ;
cin >> cmd;
//You should create the graph first!!!
if (cmd == "creategraph"){
cin >> V;
cin >> E;
}
Graph g(V,E);
while(cin >> cmd){
if(cmd == "addEdge"){
int u;
int v;
int w;
cin >> u;
cin >> v;
cin >> w;
g.addEdge(u,v,w);
}else if(cmd == "kruskalMST"){
cout<<g.kruskalMST()<<endl;
}else if(cmd == "exit"){
return 0;
}
}
return 0;
}
Hint :
1.You don’t have to use Kruskal’s algorithm, as long as you can find the total of weight in the minimum spanning tree based on the given graph.
2.Assume that all input parameters would be valid.
3. Implement the functions below:
constructor,find and merge function in the class Disjoint
kruskalMST function in class Graph
4.You can use STL and sort function.
5.In the disjoint set implementation, you can use union by height, size or rank.
6.The same edge will not be input repeatedly (for example, (1,2) and (2,1) or (1,2) and (1,2) will not be input at the same time)
7.You can use the following method to sort all edges :
sort(edges.begin(), edges.end());
8.You can declare the iterator to a vector in the following way :
vector< pair<int, iPair> >::iterator it;
9.In order to Iterate through all sorted edges, you can use the following way :
for (it=edges.begin(); it!=edges.end(); it++)
10.You can get the value of the input edge in the for loop in the following way :
Suppose the input edge is 0 1 4 (vertex 0 and vertex 1 are connected and the weight of the edge is 4)
it->second.first -> you will get 0
it->second.second -> you will get 1
it->first -> you will get 4
There are multiple lines in the input.
According to the different instructions, operating the different tasks.
Input format:
First,you will have to create a graph with vertex and edge numbers of this graph as parameters
1.Creategraph x y: create a graph with x as numbers of vertex, y as numbers of edge of this graph
Second, you will have several lines to tell you which two nodes are connected and the weight of the edge between the two nodes, the format is below.
The red part is node No.1.(The first parameter after addedge command)
The green part is node No.2.(The second parameter after addedge command)
The blue part is the weight of the edge between node 1 and 2.(The third parameter after addedge command)
Note : There is one graph in one test case.
3.kruskalMST:
Using this command will output a cost of the minimum spanning tree of the input graph
When you get "kruskalMST", you need to print out the total of weight in the minimum spanning tree and a '\n at the end.