The student is asked to write a C++ program that calculates the minimal spanning tree of a graph given node data from a file, implemented via a method in a header file.
C++ that prompts the user for a filename containing node data, reads this data to form a graph, and then outputs the minimal spanning tree (MST) of that graph. The method createSpanningGraph should be implemented in the minimalSpanTreeType.h header file. This involves creating the graph and the associated weight matrix. To solve this problem, you could follow a known MST algorithm like Kruskal's or Prim's algorithm.
To provide an example, we will consider a simplified version of the Kruskal's algorithm's implementation. This is a conceptual example and won't compile as complete code:
// Example C++ function to illustrate the idea
void createSpanningGraph(std::vector &edges) {
// sort the edges based on their weight
std::sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
return a.weight < b.weight;
});
// Initialize disjoint sets for the vertices
// ... (Disjoint set data structure implementation)
// Iterate over sorted edges and construct the minimal spanning tree
// ...
}
The sample files Ch20_Ex21Data.txt and Ch20_Ex4Data.txt are provided for testing the program.
Complete 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.
Ch20_Ex21Data.txt:
9
0 1 4 7 -999
1 0 2 4 -999
2 1 4 5 -999
3 4 6 -999
4 0 1 2 3 6 7 8 -999
5 2 7 -999
6 3 4 7 8 -999
7 0 4 5 6 -999
8 4 6 -999
0 1 2 4 3 7 2 -999
1 0 2 2 3 4 2 -999
2 1 3 4 5 5 4 -999
3 4 8 6 1 -999
4 0 3 1 3 2 5 3 8 6 2 7 3 8 15 -999
5 2 4 7 5 -999
6 3 1 4 2 7 7 8 4 -999
7 0 2 4 3 5 5 6 7 -999
8 4 15 6 4 -999
Ch20_Ex4Data.txt:
7
0 1 2 3 -999
1 0 4 6 -999
2 0 5 6 -999
3 0 4 -999
4 1 3 5 -999
5 2 4 -999
6 2 1 -999
0 1 6 2 5 3 2 -999
1 0 6 4 2 6 4 -999
2 0 5 5 7 6 5 -999
3 0 2 4 8 -999
4 1 2 3 8 5 10 -999
5 2 7 4 10 -999
6 1 4 2 5 -999