Write a program that reads, from the standard input, a description of a weighted graph with integer weights, in the input format shown below. Then the program should write, on the standard output:

the original graph G;

the edges that are part of a minimal spanning tree T of G;

the total weight of T.

For each graph, show the number of vertices and the number of edges. Make it clear just what each part of the output is. Don't make a reader guess what he or she is looking at. The output of your program might look like this.

Input graph: There are 5 vertices and 6 edges vertices weight 1 2 9 1 3 12 2 4 18 2 3 6 2 5 20 3 5 15 Minimal spanning tree: There are 5 vertices and 4 edges vertices weight 2 3 6 1 2 9 3 5 15 2 4 18 The total weight of the spanning tree is 48.

Do not confuse edges with vertices. Keep track of the number of vertices in a graph separately from the number of edges. Remember that the first number in the input is the number of vertices, not the number of edges.

The vertices are numbered 1, , n. You will need to have an array of edges. It is a good idea to start numbering the edges from 0, not from 1. So put the first edge that you read at index 0 in the array of edges.

An object of type Edge represents one edge in a graph. It has three fields: two vertex numbers and a weight. Include a parameterless constructor that sets all three fields to 0.

An object of type Graph represents a weighted graph. It has four fields:

the number of vertices in the graph,

the number of edges in the graph,

an array of Edge structures that holds the edges,

the physical size of that array of edges.

Choose clear and sensible names for the fields.

Include a constructor Graph(nv) that yields a graph with nv vertices and no edges. The constructor must create the array of edges.

Since you need to create the array of edges before you know how many edges there are, you will need to set a fixed array size. You can assume that there are no more than 100 edges, but that number must be easy to change. To increase the maximum number of edges to 200, for example, should only require changing only one line of your program. To achieve that, create a named constant that is the maximum number of edges. For example,

 const int maxNumEdges = 100; 

defines constant maxNumEdges with a value of 100. Any time you need to refer to the maximum number of edges, use maxNumEdges, not 100.

Note. The physical-size field should be set to maxNumEdges by the constructor. When you want to know the size of the array of edges in g, use g.physicalSize (or whatever you have called that field), not maxNumEdges. The reason is that it is is possible that you add another Graph constructor later that creates an array whose size is not maxNumEdges. You would prefer not to be forced to edit the rest of the code when you do that.

Software developers frequently think about doing things in ways that make the software easy to modify later. Mostly, that is the result of having not done it in the past, and having spent long hours changing things that should have been easy to change.

Do not confuse the physical size of the array with the current number of edges. The physical size is the maximum number of edges allowed. The current number of edges might be less than that.

All structure types must be documented by saying

what an object of this structure type represents and

what property of the object each field represents.

In mst.cpp, define a function insertEdge(u, v, w, g) that adds an edge between u and v of weight w to graph g. If the edge array is full, insertEdge must refuse to add the edge.

Here is a suitable contract for insertEdge. Note its similarity to the preceding paragraph.

 // insertEdge(u, v, w, g) inserts an edge of weight w between vertices // u and v into graph g. // // If there is not enough room in g to add the edge, then // insertEdge does nothing. 

Pass g by pointer to insertEdge. Otherwise, insertEdge will modify a (shallow) copy of your graph, which is not what you want. So the type of parameter g should be Graph*.

Here is a suitable heading for insertEdge.

 void insertEdge(vertexNum u, vertexNum v, int w, Graph* g) 

Make sure that insertEdge does the whole job of inserting an edge. Don't force its caller to do part of the job. Increasing the number of edges is part of the job.