All information about coding project is contained in this album: https://imgur.c

Question

All information about coding project is contained in this album: https://imgur.com/a/iJgRW

After you read in the matrix, print it out so I can make sure that you read it in correctly. (Teacher note)

On the last page of the album, there is a typo of the weight of the graph, it is 1397, not 1297

I'll give a bit more clarification on the input of the WAM. They are going to input X amount of elements seperated by spaces then press enter and continue with the second line. The objective is to figure out the amount of elements in the first line and ask for X - 1 more lines of numbers, to ensure that the matrix is square.

Explanation / Answer

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cassert>
#include <cmath>
#include <cstring>
#include <sstream>
#include <limits.h>

#define si(n) scanf("%d",&n)
#define sd(n) scanf("%lf",&n)
#define sl(n) scanf("%lld",&n)
#define ss(str) scanf("%s",str)
#define FOR(i,a,b) for(int i = a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pii pair<int,int>

typedef long long int ll;
typedef unsigned long long int ull;

using namespace std;

int size;
int minKey(vector<int> key, vector<bool> mstSet)
{
   int min = INT_MAX, minIndex;

   for(int v = 0; v < size; v++) {
       if(mstSet[v] == false && key[v]<min){
           min = key[v];
           minIndex = v;
       }
   }

   return minIndex; //returns the minimum next vertex in MST.
}

//void printMST(vector<vector<int> >parent) {
void printMST(vector<int>parent, vector< vector<int> > graph) {

   cout<<"The output from Prim's Algorithm is: ";

   vector< vector<int> > output;
   vector<int> init(size,0);
   int mstSum = 0;
     for (int i = 0; i < size; i++)
       output.push_back(init);

   for(int i = 1;i<size;i++){
       //cout << parent[i] <<" "<<i<<endl;;
       output[parent[i]][i] = output[i][parent[i]] = graph[i][parent[i]];
       mstSum += graph[i][parent[i]];
   }

   for(int i = 0;i<size;i++){
       for(int j = 0;j<size;j++){
           cout<<output[i][j]<<" ";
       }
       cout<<endl;
   }

   cout<<"The total weight of the graph is "<<mstSum<<endl;;
}
void prims(vector< vector<int> > graph)
{
     vector<int> key(size);   // Key values used to pick minimum weight edge in cut
     vector<bool> mstSet(size); // To represent set of vertices not yet included in MST
   //vector< vector<int> > parent;
   vector< int > parent(size);

     // Initialize all keys as INFINITE
     for (int i = 0; i < size; i++)
        key[i] = INT_MAX, mstSet[i] = false;

   //vector<int> init(size,0);
     //for (int i = 0; i < size; i++)
       //parent.push_back(init);

     // Always include first 1st vertex in MST.
     key[0] = 0;     // Make key 0 so that this vertex is picked as first vertex
     parent[0] = 0; // First node is always root of MST

     // The MST will have V vertices
     for (int count = 0; count < size-1; count++)
     {
        // Pick the minimum key vertex from the set of vertices
        // not yet included in MST
        int u = minKey(key, mstSet);
       //cout<<u<<endl;

        // Add the picked vertex to the MST Set
        mstSet[u] = true;

        // Update key value and parent index of the adjacent vertices of
        // the picked vertex. Consider only those vertices which are not yet
        // included in MST
        for (int v = 0; v < size; v++)

           // graph[u][v] is non zero only for adjacent vertices of m
           // mstSet[v] is false for vertices not yet included in MST
           // Update the key only if graph[u][v] is smaller than key[v]
          if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
             parent[v] = u, key[v] = graph[u][v];
     }

     // print the constructed MST
     printMST(parent, graph);
}

int find(int i, vector<int> &krusParent){
   while(krusParent[i] != -1) {
       i = krusParent[i];
   }
   return i;
}

int uni(int i, int j, vector<int> &krusParent) {
   if(i != j) {
       krusParent[j] = i;
       return 1;
   }
   return 0;
}

void kruskal(vector< vector<int> >graph){

   vector<int> krusParent(size, -1);
   vector< vector<int> > G = graph;
   vector<int> edge(size);
   int count = 1,u,v,a,b;
   int minCost = 0;
   cout << size;
   while(count < size) {
       int min = INT_MAX;

       //Finding the minimum edge;
       for(int i = 0;i <size; i++) {
           for(int j = 0;j <size; j++) {

               if(G[i][j]!=0 && G[i][j] < min) {
                   min = G[i][j];
                   u = a = i;
                   v = b = j;
               }
           }
       }

       u = find(u,krusParent);
       v = find(v,krusParent);
       //cout<<u<<" "<<v;
       if(uni(u,v,krusParent))
       {
           edge[a] = b;
           minCost += min;
           //cout<<a<<" "<<b<<" "<<min<<endl;
           count++;
       }
       G[a][b] = G[b][a] = 0;
   }
   cout<<"The output from Kruskal's Algorithm is: ";

   vector< vector<int> > output;
   vector<int> init(size,0);
   int mstSum = 0;
     for (int i = 0; i < size; i++)
       output.push_back(init);

   for(int i = 0;i<size;i++){
       //cout << parent[i] <<" "<<i<<endl;;
       output[edge[i]][i] = output[i][edge[i]] = graph[i][edge[i]];
       mstSum += graph[i][edge[i]];
   }

   for(int i = 0;i<size;i++){
       for(int j = 0;j<size;j++){
           cout<<output[i][j]<<" ";
       }
       cout<<endl;
   }

   cout<<"The total weight of the graph is "<<mstSum<<endl;;

  
}

int main()
{
   cout<<"Enter WAM: ";

   std::string input;
   getline(cin, input);

   istringstream iss(input);
   int temp ;
   vector<int> initial;
   //vector< vector< int > >graph;

   while(iss >> temp) {
       size++;
       initial.push_back(temp);
   }
   vector< vector<int> > graph;
   graph.push_back(initial);

   for(int i = 1; i<size;i++) {
       initial.clear();
       for(int j = 0; j<size;j++) {
           cin>>temp;
           initial.push_back(temp);
       }
       graph.push_back(initial);
   }

   cout<< "Input graph is : ";
   for(int i =0;i<size;i++){
       for(int j =0;j<size;j++){
           cout<<graph[i][j]<<" ";
       }
       cout<<endl;
   }

   kruskal(graph);
   prims(graph);
  
  
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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