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
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 Prims 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 Prims 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
#include
#include
#include
#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 << "("< << 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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started