Hello, I need immediate help with the following C++ assignment. The objective is
ID: 3692243 • Letter: H
Question
Hello, I need immediate help with the following C++ assignment. The objective is to write a definatition of function PRIM2, a new version of PRIM's algorithm
requirements and specifications are listed below, as well as a copy of class msTreeType:
ThankYou in advance...
Text book C++ Programming – Program Design Including Data Structures. 7th Edition D.S. Malik
Chapter 20 Graphs – Programing exercise #5
The algorithm to determine the minimal spanning tree given in this chapter is of the order O(n3). The following is an alternative to Prim’s algorithm that is of order O(n2).
Write a definition of the new function (Prim2) to implement this algorithm, and add this function to the class msTreeType.
Furthermore, write a program to test this new Prim’s algorithm.
Input: A connected weighted graph G = (V, E) of N vertices, numbered 0, 1, 2,,,, n-1; starting with vertex s, with a weight matrix of W.
Output: The minimal spanning tree.
Prim2 (G, W, n, s)
Let T = (V, E), where E = 0
for ( j = 0; j < n; j ++) to n
{
edgeWeights [ j ] = W(s, j);
edges [ j ] = s;
visited [ s ] = false;
}
edgeWeights [ s ] = 0;
visited [ s ] = true
while (not all nodes are visited)
{
Choose the node that is not visited and has the smallest weight, and call it k.
visited [ k ] = true;
E = E U { ( k, edges [ k ] ) }
V = V U { k }
for each node j that is not visited
if (W ( k, j ) < edgeWeights [ j ])
{
edgeWeights [ j ] = W ( k, j );
edges[ j ] = k;
}
return T;
*************************************************************************************
class msTreeType
#ifndef H_msTree
#define H_msTree
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cfloat>
#include "graphType.h"
using namespace std;
class msTreeType: public graphType
{
public:
void createSpanningGraph();
//Function to create the graph and the weight matrix.
//Postcondition: The graph using adjacency lists and
// its weight matrix is created.
void minimalSpanning(int sVertex);
//Function to create a minimal spanning tree with
//root as sVertex.
// Postcondition: A minimal spanning tree is created.
// The weight of the edges is also
// saved in the array edgeWeights.
void printTreeAndWeight();
//Function to output the edges of the minimal
//spanning tree and the weight of the minimal
//spanning tree.
//Postcondition: The edges of a minimal spanning tree
// and their weights are printed.
msTreeType(int size = 0);
//Constructor
//Postcondition: gSize = 0; maxSize = size;
// graph is an array of pointers to linked
// lists.
// weights is a two-dimensional array to
// store the weights of the edges.
// edges is an array to store the edges
// of a minimal spanning tree.
// egdeWeight is an array to store the
// weights of the edges of a minimal
// spanning tree.
~msTreeType();
//Destructor
//The storage occupied by the vertices and the arrays
//weights, edges, and edgeWeights is deallocated.
protected:
int source;
double **weights;
int *edges;
double *edgeWeights;
};
void msTreeType::createSpanningGraph()
{
cout << "Write the definition of the function "
<< "createSpanningGraph." << endl;
} //createWeightedGraph
void msTreeType::minimalSpanning(int sVertex)
{
int startVertex, endVertex;
double minWeight;
source = sVertex;
bool *mstv;
mstv = new bool[gSize];
for (int j = 0; j < gSize; j++)
{
mstv[j] = false;
edges[j] = source;
edgeWeights[j] = weights[source][j];
}
mstv[source] = true;
edgeWeights[source] = 0;
for (int i = 0; i < gSize - 1; i++)
{
minWeight = DBL_MAX;
for (int j = 0; j < gSize; j++)
if (mstv[j])
for (int k = 0; k < gSize; k++)
if (!mstv[k] && weights[j][k] < minWeight)
{
endVertex = k;
startVertex = j;
minWeight = weights[j][k];
}
mstv[endVertex] = true;
edges[endVertex] = startVertex;
edgeWeights[endVertex] = minWeight;
} //end for
} //end minimalSpanning
void msTreeType::printTreeAndWeight()
{
double treeWeight = 0;
cout << "Source Vertex: " << source << endl;
cout << "Edges Weight" << endl;
for (int j = 0; j < gSize; j++)
{
if (edges[j] != j)
{
treeWeight = treeWeight + edgeWeights[j];
cout << "("<<edges[j] << ", " << j << ") "
<< edgeWeights[j] << endl;
}
}
cout << endl;
cout << "Minimal Spanning Tree Weight: "
<< treeWeight << endl;
} //end printTreeAndWeight
//Constructor
msTreeType::msTreeType(int size)
:graphType(size)
{
weights = new double*[size];
for (int i = 0; i < size; i++)
weights[i] = new double[size];
edges = new int[size];
edgeWeights = new double[size];
}
//Destructor
msTreeType::~msTreeType()
{
for (int i = 0; i < gSize; i++)
delete [] weights[i];
delete [] weights;
delete [] edges;
delete edgeWeights;
}
#endif
Explanation / Answer
import java.io.*;
import java.text.*;
import java.util.*;
public class MSTree extends Graph
{
protected int source;
protected double[][] weights;
protected int[] edges;
protected double[] edgeWeights;
public MSTree()
{
super();
weights = new double[maxSize][maxSize];
edges = new int[maxSize];
edgeWeights = new double[maxSize];
}
public MSTree(int size)
{
super(size);
weights = new double[maxSize][maxSize];
edges = new int[maxSize];
edgeWeights = new double[maxSize];
}
public void createSpanningGraph() throws IOException, FileNotFoundException
{
System.out.println("Create Spanning Graph");
}
public void minimalSpanning(int sVertex)
{
int i,j,k;
int startVertex = 0, endVertex = 0;
double minWeight;
source = sVertex;
boolean[] mstv = new boolean[maxSize];
for(j = 0; j < gSize; j++)
{
mstv[j] = false;
edges[j] = source;
edgeWeights[j] = weights[source][j];
}
mstv[source] = true;
edgeWeights[source] = 0;
for(i = 0; i < gSize - 1; i++)
{
minWeight = infinity;
for(j = 0; j < gSize; j++)
if(mstv[j])
for(k = 0; k < gSize; k++)
if(!mstv[k] && weights[j][k] < minWeight)
{
endVertex = k;
startVertex = j;
minWeight = weights[j][k];
}
mstv[endVertex] = true;
edges[endVertex] = startVertex;
edgeWeights[endVertex] = minWeight;
}
}
public void printTreeAndWeight()
{
double treeWeight = 0;
DecimalFormat twoDigits = new DecimalFormat("0.00");
System.out.println("Source Vertex: " + source);
System.out.println("Edges Weight");
for(int j = 0; j < gSize; j++)
{
if(edges[j] != j)
{
treeWeight = treeWeight + edgeWeights[j];
System.out.println("(" + edges[j] + ", " + j + ") "
+ twoDigits.format(edgeWeights[j]));
}
}
System.out.println();
System.out.println("Minimal Spanning Tree Weight: "
+ twoDigits.format(treeWeight));
}
public void Prim2(int i)
{
int G;int W; int n = 0; int s = 0;
boolean[] visited = null;
for(int j=0;j<n;j++)
{
edgeWeights[j]=weights[s][j];
edges[j]=s;
visited[j]=false;
}
edgeWeights[s]=0;
visited[s]=true;
while(!visited[i]){
int k = 0;
visited[k]=true;
for(int j=0;j<n;j++)
if(weights[k][j])<edgeWeights[j])
{
edgeWeights[j] = weights[k][j]);
Edges[j] = k;
}
}
Return i;
}
Main.Class
import java.io.FileNotFoundException;
import java.io.IOException;
public class Prim_Class
{
public static void main(String[]args)
{
MSTree myTree = new MSTree(8);
try {
myTree.createSpanningGraph();
}
catch (FileNotFoundException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
catch (IOException e)
{
// TODO Auto-generated catch block
e.printStackTrace();
}
myTree.printGraph();
myTree.printTreeAndWeight();
myTree.minimalSpanning(2);
myTree.printTreeAndWeight();
myTree.Prim2(2);
myTree.printTreeAndWeight();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.