Write a function in main.cpp, which creates a random graph of a certain size as follows. The function takes two parameters. The first parameter is the number of vertices n. The second parameter p (1 >= p >= 0) is the probability that an edge exists between a pair of nodes. In particular, after instantiating a graph with n vertices and 0 edges, go over all possible vertex pairs one by one, and for each such pair, put an edge between the vertices with probability p. (Thus, there is no edge between the vertices with probability 1-p).

In the main function, create a graph with 10,000 (ten thousand) vertices, and experiment the following. Pick some p to create the edges of the graph, and then determine the number of components of the graph (Write a function to do this. How do you do this? I talked about this in the class). Remember the extreme cases: for p = 0, there are no edges in the graph so that the number of components is the number of vertices, which is 10,000. For p = 1, we have the complete graph so that the graph is certainly connected, the number of components is 1.

Now by experiment, determine when the graph becomes connected as you increase from p = 0 up to p = 1. As a mathematical fact, there is some value p such that for values smaller than p, the graph has more than one component. After the probability hits p and goes higher, the graph suddenly becomes connected. Try to determine this value of p. Write your result as a comment in your code

2) Now, extend your function creating a random graph so as to assign weights to the edges. The edges will have random integer weights in the range [1...10]. Make sure you select some p so as to make the graph connected. Implement Prims algorithm in a function. Then run it on this graph and calculate the cost of the minimum spanning tree. You may get help online for the implementation of Prims algorithm.

------------------------------------------------------------------

Main.cpp

#include

#include "Graph.h"

using namespace std;

int main()

{

Graph g(5);

cout << g.getNumVertices() << endl;

Edge e(4,1,1);

g.add(e);

cout << g.getNumEdges() << endl;

return 0;

}