Write a program (in main.cpp) that: Prompts the user for a filename containing node data. Outputs the minimal spanning tree for a given graph. You will need to implement the createSpanningGraph method in minimalSpanTreeType.h to create the graph and the weight matrix. Note:
Write a program (in main.cpp) that: Prompts the user for a filename containing node data. Outputs the minimal spanning tree for a given graph. You will need to implement the createSpanningGraph method in minimalSpanTreeType.h to create the graph and the weight matrix. Note:
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
Write a program (in main.cpp) that:
- Prompts the user for a filename containing node data.
- Outputs the minimal spanning tree for a given graph.
You will need to implement the createSpanningGraph method in minimalSpanTreeType.h to create the graph and the weight matrix.
Note: Files Ch20_Ex21Data.txt and Ch20_Ex4Data.txt contain node data that you may test your program with.
minimalSpanTreeType.h :
#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()
{
// TODO: Implement createSpanningGraph
} //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
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education