generate random graphs, check whether graphs are connected, and construct minimum spanning trees. You should represent graphs using the MatrixGraph class from lectures. Do not modify this class.

1) Setting up

Create a class called ConnectedCitiesGraph. Add a method static Graph getRandomCities(int n) which creates a randomly weighted undirected graph with n vertices (minimum 5, maximum 20). The graph should contain every possible edge, and each edge should have a randomly chosen double weight between 1 and 10 inclusive. You can create 20 cities but not all cities need to be in the Graph (based on the chosen n).

2 )Total edge weight

Add a method double getTotalEdgeWeight (Graph g) which returns the total weight of the edges in g. The method should work correctly for both directed and undirected graphs.

2.1 Connectivity

Write a method static boolean isConnected (source, destination) which determines whether the given source city can reach a destination city. Use breadth-first search mark the vertices that have been visited and, at the end of the search, check that every vertex is visited. You should avoid adding any vertex to the queue more than once.

3) Shortest Path

Write a method static void getShortestPath (source, destination) which will find the shortest path from source to destination. If there is such a path, list the path and show the cost of traveling. If there is no such path, then show that there is no such path and show the cost of traveling as 0.

4) Test code

Add a main method to your class. It should perform the following tests.

a) Compute the total weight of the graph, using the s u p p l i e d class GraphOfEssex.

b) Create 20 random graphs with 10 to 20 vertices each, created with getRandomCities(). Compute the shortest distance from source to destination (source being the 1st city and destination being the last city. Eg. If there are 10 cities generated, then the source is the 1st city and the destination is the 10th city)