Question

In this problem, you are expected to implement Prim's Algorithm on an undirected simple graph. Write a method that is part of a class that implements Graph as an adjacency matrix. This method should generate a minimum spanning tree using Prim's Algorithm, and print out the edge added by the algorithm on each iteration. 3 10 4 8 Output: 1 2 1 3 34 35 5 6 17 3 12 34 5 1 6 8 20 4 Output: 26 65 53 34 3 1

Answer 1

Ans:

Program (Language : CPP)

#define MAXNUMVERTICES 108
#include <iostream>
#include <set>
#include <vector>
#include <map>
#include <climits>
using namespace std;

class Graph{
   private:
   int theGraph[MAXNUMVERTICES][MAXNUMVERTICES]={0};      //Adjacency matrix storing the graph
   set<int> vertices;                                     //Set storing all the vertices
   public:
   void insertEdge(int from, int to, int weight);         //Method to insert edge
   void insertVertex(int x);                   //Method to insert vertex in set
   void primMST();                           //Method for finding minimum spanning tree
   bool checkValidity(vector<bool> &inMST,int from, int to);    //Method checking edge can be added to MST or not at each step
};

void Graph::insertEdge(int to, int from, int weight){      //Method Defination
   this->theGraph[to][from] = weight;
   this->theGraph[from][to] = weight;
   }
  
void Graph::insertVertex(int x){                          //Method Defination
   this->vertices.insert(x);
}

bool Graph::checkValidity(vector<bool> &inMST,int from, int to){    
   if(from==to)                       // if both vertices are same
          return 0;
    if(inMST[from]==0 && inMST[to]==0) //if both vertices are not in MST
           return 0;
    if (inMST[from]==1 && inMST[to]==1) //if both vertices are already in MST
           return 0;
   return 1;
}

void Graph::primMST(){
  
    int V = (int) this->vertices.size();
    vector<bool> inMST(V+1, 0);
   // include first vertex in MST
    inMST[1] = true;
   // keep adding edges while number of included edges does not become V-1
    int edge_count = 0, mincost = 0;    // mincost stores the MST minimum cost
    while(edge_count<(V-1)){
                                       // Find minimum weight valid edge
        int min = INT_MAX, a = -1, b = -1;
        for(int i = 1; i <=V ; i++){
            for(int j = 1; j <=V ; j++){              
                if(this->theGraph[i][j] < min && this->theGraph[i][j]!=0){
                    if(this->checkValidity(inMST,i, j)){
                        min = this->theGraph[i][j];
                        a = i;
                        b = j;
                    }
                }
            }
        }
      
        if(a!=-1 && b!=-1){
           cout<<a<<" "<<b<<endl;         //print out the added edge
           edge_count++;
            mincost = mincost + min;
            inMST[b] = 1;
            inMST[a] = 1;
        }
    }
}

int main(){
   Graph *myGraph = new Graph();
   int numEdges, inVert, outVert, wt;
   std::cin>>numEdges;
   for(int i=0; i<numEdges; i++){                 //Reading graph and storing it in matrix
       std::cin>>inVert;
       std::cin>>outVert;
       std::cin>>wt;
       myGraph->insertEdge(inVert, outVert, wt);
       myGraph->insertVertex(inVert);
       myGraph->insertVertex(outVert);
   }
   myGraph->primMST();
}

Code Screenshots

1 #define MAXNUMVERTICES 108 2 #include <iostream> 3 #include <set> 4 #include <vector> 5 #include <map> 6 #include <climits> 7 using namespace std; class Graph{ 10 private: 11 int theGraph[MAXNUMVERTICES][MAXNUMVERTICES ]={C}; //Adjacency matrix storing the graph 12 set int> vertices; //Set storing all the vertices 13 public: 14 void insertEdge(int from, int to, int weight); //Method to insert edge 15 void insertVertex(int x); //Method to insert vertex in set 16 void primMST(); //Method for finding minimum spanning tree 17 bool checkvalidity(vector<bool> &inMSt, int from, int to); //Method checking edge can be added to MST or not at each step 18 }; 19 20 void Graph::insertEdge(int to, int from, int weight) { //Method Defination 21 this->theGraph[to][from] = weight; 22 this->theGraph[from][to] = weight; 23 24 25 void Graph::insertVertex(int x){ //Method Defination 26 this->vertices.insert(x); 27 } }

28 29 bool Graph::checkvalidity (vector<bool> &inMST, int from, int to){ 30 if(from==to) // if both vertices are same 31 return 0; 32 if(inMST[from]==0 && inMST[to]==0) //if both vertices are not in MST 33 return 0; 34 if (inMST[from]==1 && inMST[to]==1) //if both vertices are already in MST 35 return 0; 36 return 1; 37 } 38 39 void Graph::primMST(){ 40 41 int V = (int) this->vertices.size(); 42 vector<bool> inMST(V+1, 0); 43 // include first vertex in MST 44 inMST[1] = true; 45 // keep adding edges while number of included edges does not become V-1 46 int edge_count = 0, mincost = 0; // mincost stores the MST minimum cost 47 while (edge_count (V-1)){ 48 // Find minimum weight valid edge 49 int min = INT_MAX, a = -1, b = -1; 50 for(int i = 1; i <=V ; i++){ 51 for(int j = 1; j <=V ; j++){ 52 if(this->theGraph[i][j] < min && this->theGraph[i][j]!=0) { 53 if(this->checkvalidity(inMST, i, j)){ 54 min = this->theGraph[i][j]; 55 a = i; 56 b = j; بها } 59

} سها 60 61 62 if(a!=-1 && b!=-1){ 63 cout<<a<<" "<<b<<endl; //print out the added edge 64 edge_count++; 65 mincost = mincost + min; 66 inMST[b] = 1; 67 inMST[a] = 1; 68 69 70 } 71 72 int main({ 73 Graph *myGraph = new Graph(); 74 int numEdges, invert, outVert, wt; 75 std::cin>>numEdges; 76 for(int i=0; i<numEdges; i++) { //Reading graph and storing it in matrix 77 std::cin>>invert; 78 std::cin>>outVert; 79 std::cin>>wt; 80 myGraph->insertEdge(invert, outVert, wt); 81 myGraph->insertVertex(invert); 82 myGraph->insertVertex (outVert); 83 84 myGraph->primMST(); 85 }

Input

18 212 1 3133 4147 5236 64 32 736 10 8358 9564 10

Output

12 13 34 35 56