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. 7^th 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(n³). The following is an alternative to Prims algorithm that is of order O(n²).

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