The algorithm to determine the minimal spanning tree given in this chapter is of
ID: 3770376 • Letter: T
Question
The algorithm to determine the minimal spanning tree given in this chapter is of the order O(n^3). The following is an alternative to Prim's algorithm that is of the order O(n^2). A connected weighted graph G = (V, E) of n vertices, numbered 0, 1, ..., n; starting with vertex s, with a weight matrix of W. The minimal spanning tree. Write a definition of the function Prim2 to implement this algorithm, and also add this function to the class msTreeType. Furthermore, write a program to test this version of Prim's algorithm.Explanation / Answer
#ifndef H_msTree
#define H_msTree
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include "GraphType_H.h"
using namespace std;
template <class vType, int size>
class msTreeType: public graphType <vType, size>
{
public:
void createSpanningGraph( int noOfNodes ); //- Function to create the graph and the weight matrix.
void minimalSpanning( vType sVertex ); //- Function to create the edges of the minimal spanning tree. The weight of the edges is also saved in the array edgeWeights.
void printTreeAndWeight(); //- Function to output the edges and the weight of the minimal spanning tree.
void prim2MST( vType sVertex ); weighted graph G = (V,E) where V is set of Vertices(nodes) & E is set of Edges(links between nodes)
int readNoOfNodesFromGraphFile();
protected:
vType source;
double weights[size][size];
int edges[size];
double edgeWeights[size];
private:
void printGraphForCase1( int Graph[][7] );
void printGraphForCase2( int *tempArray );
void printGraphForCase3( int **tempArray );
};
template <class vType, int size>
int msTreeType <vType, size> :: readNoOfNodesFromGraphFile()
{
int countSize = 0;
ifstream myInputFile;
myInputFile.open( "file1.txt" );
if ( !myInputFile )
{
cout << "Cannot open the input file." << endl;
return -1;
}
while( !myInputFile.eof() )
{
int edgeWeightInputData;
myInputFile >> edgeWeightInputData;
if ( myInputFile.fail() )
{
cout << "Error bad input, please check the graph.txt file for invalid input" << endl;
return -1; that the user can re-enter a valid file
}
countSize++;
}
myInputFile.close();
int arraySize = sqrt( countSize );
return arraySize;
}
template <class vType, int size>
void msTreeType <vType, size> :: createSpanningGraph( int noOfNodes )
{
if (noOfNodes == 0)
{
std::cout << "Input Graph is figure 12.16 from C++ textbook by D.S Malik" << std::endl;
int noOfVertices = 7;
gSize = noOfVertices;
int Graph[7][7] =
{
{ 0,6,5,2,0,0,0 }, //- Row 0
{ 6,0,0,0,2,0,4 }, //- Row 1
{ 5,0,0,0,0,7,5 }, //- Row 2
{ 2,0,0,0,8,0,0 }, //- Row 3
{ 0,2,0,8,0,10,0 }, //- Row 4
{ 0,0,7,0,10,0,0 }, //- Row 5
{ 0,4,5,0,0,0,0 } //- Row 6
}; //- Initialising the graph to the above matrix
for ( int i = 0; i < noOfVertices; i++ ) //- Looping for Row
{
for ( int j = 0; j < noOfVertices; j++ ) //- Looping for Col
{
weights[i][j] = infinity; //- Settting to the constant infinity. So we can compare edgeweight later on by using <
if ( Graph[i][j] != 0 ) //- Check to see if there is a link. 0 means no link
{
graph[i].insertedgeWeightInputDataAtTail(j); //- Creating the adjacentList of nodes
weights[i][j] = Graph[i][j]; //- Adding the weight of the matrix
}
}
}
printGraphForCase1( Graph ); //- Printing out the input graph as a matrix
}
else if ( noOfNodes < 0 )
{
std::cout << "Input Graph is from the graph.txt file"<< " " << std::endl;
int countSize = 0;
int inputGraphArray[size]; edgeWeightInputData from the graph.txt
ifstream myInputFile; //- Create input stream
myInputFile.open( "graph.txt" );
if ( !myInputFile ) //- If cannot open file then return the user to the main function.
{
cout << "Cannot open the input file." << endl;
return; //- Return to main.cpp if cannot open
}
while( !myInputFile.eof() )
{
int edgeWeightInputData; //- To store the edgeWeight from the file
myInputFile >> edgeWeightInputData; //- Reading the edgeWeight from the file
if ( myInputFile.fail() ) //- Returns to the main if the file contains bad data e.g alpha char's instead of int's
{
cout << "Error bad input, please check the graph.txt file for invalid input" << endl;
return;
}
inputGraphArray[countSize] = edgeWeightInputData; //- Used for Testing Purposes
countSize++;
}
myInputFile.close();
gSize = sqrt( countSize );
int k = 0; //- Keep count of single dim array element position
for ( int i = 0; i < gSize; i++ ) //- Loop for Row
{
for ( int j = 0; j < gSize; j++ ) //- Loop for Col
{
weights[i][j] = infinity; //- Settting to constant infinity. So we can compare edgeweight later on by using <
if ( inputGraphArray[i*gSize+j]!= 0 ) //- Check to see if there is a link. 0 means no link
{
graph[i].insertedgeWeightInputDataAtTail( k ); //- Creating the adjacentList of nodes
weights[i][j] = inputGraphArray[k]; //- adding the weight of the matrix
}
k++; //- Iterating through the single dem array element position
}
}
printGraphForCase2(inputGraphArray); //- Printing out the input graph as a matrix
} //- End of Else If - noOfNodes < 0
else if ( noOfNodes > 0 ) //- Case 3: Randomly generate number of edges between nodes and their edgeweights. PLEASE NOTE: noOfNodes must be < maxSize
{
std::cout << "Input Graph will be generated randomly with " << noOfNodes
<< " Nodes." << " " << std::endl;
srand ( ( unsigned ) time( NULL ) ); //- Initialize random seed
gSize = noOfNodes;
int maxNoOfEdges = ( ( noOfNodes*( noOfNodes - 1 ) )/2 ); //- Max edges formula is: n(n-1)/2
if ( maxNoOfEdges == 0 ) //- If 1 node is entered then there is a chance there will be no links
{
maxNoOfEdges = 1;
}
int noOfEdges = rand() % maxNoOfEdges + 1; //- generates random number of edges between (1 - maxNoOfEdges) for the graph
while (noOfEdges < noOfNodes) //- ensure there are enough edges for there to be a link between each node
{
noOfEdges+=1; //- increasing size by 1
}
int* randEdgeWeightArray = new int [noOfEdges]; //- array containing random weights for the edges
for ( int i = 0; i < noOfEdges; i++ )
{
randEdgeWeightArray[i] = rand() % maxNoOfEdges + 1; //- Setting element values of the randEgeWeightArray
//std::cout << "Random EdgeWeight is: " << randEdgeWeightArray[i] << std::endl;
}
//std::cout << "The max number of Edges in this graph are: " << noOfEdges << std::endl; //- Used for testing purposes
int** tempArray = new int* [noOfNodes]; //- Creating 2d array with pointers
for ( int i = 0; i < noOfNodes; i++ )
{
tempArray[i] = new int[noOfNodes]; //- Creating new row of ints
}
//- Loop for initialising tempArray
for ( int i = 0; i < noOfNodes; i++ ) //- Looping for Row
{
for ( int j = 0; j < noOfNodes; j++ ) //- Looping for Col
{
tempArray[i][j] = 0; //- Initialising to 0
}
}
int counter = 0; //- Stores the count
for ( int i = 0; i < noOfNodes; i++ ) //- Looping for Row
{
int emptyCounter = 0; //- To check and make sure each node has one conection
for ( int j = 0; j < noOfNodes; j++ ) //- Looping for Col
{
if ( i == j ) //- Check for ensuring the diaganol is always 0. As nodes can not link to itself in this graph.
{
}
else
{
int randNo =( rand() % (501 - 499) ) + 499; //- Used to randomly allocate the links between nodes with magic numbers
if ( randNo == 499 )
{
}
else if ( counter < noOfEdges ) //- Check to ensure that we do not add more edges then we have created
{
tempArray[i][j] = randEdgeWeightArray[counter]; //- Setting the element to the random edge weight
tempArray[j][i] = randEdgeWeightArray[counter]; //- Setting the element to the random edge weight and ensures that it is symetrical
counter++; //- Iterating the count by 1
emptyCounter++; //- Iterating the emptyCount by 1
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.