Data Structures and Algortihms in JAVA This part of the assignment is about graph algorithms. You will 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.

2.1 Setting up (7%)

Create a class called MST. Add a method static Graph getRandomGraph(int n) which cre- ates a randomly weighted undirected graph with n vertices. The graph should contain every possible edge, and each edge should have a randomly chosen double weight between 0 and 10.

2.2 Total edge weight (7%)

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.

(You could test your method for undirected graphs using the GraphOfEssex class, but you are not required to do this.)

2.3 Connectivity (12%)

Write a method static boolean isConnected (Graph g) which determines whether the given graph g is connected. Use the following algorithm.

Create a queue and add an arbitrary vertex (e.g., vertex 0) to it. Create an array of booleans to store whether each vertex has been visited While the queue is not empty:

Remove the first vertex from the queue. Mark this vertex as visited. Add all of its unvisited neighbours to the queue.

Finally, check whether all vertices have been visited.

You may use Javas ConcurrentLinkedQueue for the queue, which is in the package java.util.concurrent. Note that this class uses the name poll for the operation that I called remove in the lectures.

2.4 Minimum spanning trees (12%)

Write a method static void makeMST (Graph g) which replaces the graph g with its min- imum spanning tree. You must compute the minimum spanning tree in the following way:

create a list of the graphs edges, in decreasing order of weight;

for each edge in turn, delete that edge from the graph if the resulting graph is connected.

The resulting graph is a minimum spanning tree.1 Your code may assume that the input graph g is connected. I have supplied the file Edge.java, which you may use and adapt if you wish. If you do

use it, please include it in the file MST.java. You may use Javas standard list classes, and you may use Collections.sort() to sort the list.

2.5 Test code (8%)

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

1. a) Compute the MST of the graph of Essex from lectures, using the class GraphOfEssex

   which I have supplied. Check that the MST has weight 95.

2. b) ComputetheMSTsof20randomgraphswith100verticeseach,createdwithgetRandomGraph(). Compute and print the average weight of these MSTs. (The answer should be between about 11.2 and 12.5.) #GraphOfEssex.java public class GraphOfEssex { public static final int BASILDON = 0; public static final int BRENTWOOD = 1; public static final int BRAINTREE = 2; public static final int CHELMSFORD = 3; public static final int CLACTON = 4; public static final int COLCHESTER = 5; public static final int HARLOW = 6; public static final int HARWICH = 7; public static final int RAYLEIGH = 8; public static final int SOUTHEND = 9; public static final int WITHAM = 10;

   public static final String[] TOWN = {"Basildon", "Brentwood", "Braintree", "Chelmsford", "Clacton", "Colchester", "Harlow", "Harwich", "Rayleigh", "Southend", "Witham"};

   public static Graph getGraph () { MatrixGraph g = new MatrixGraph (11, Graph.UNDIRECTED_GRAPH);

   g.addEdge (BASILDON, BRENTWOOD, 8); g.addEdge (BASILDON, CHELMSFORD, 12); g.addEdge (BASILDON, RAYLEIGH, 4); g.addEdge (BASILDON, SOUTHEND, 10); g.addEdge (BRENTWOOD, CHELMSFORD, 11); g.addEdge (BRENTWOOD, HARLOW, 14); g.addEdge (BRENTWOOD, RAYLEIGH, 13); g.addEdge (BRAINTREE, CHELMSFORD, 10); g.addEdge (BRAINTREE, COLCHESTER, 15); g.addEdge (BRAINTREE, HARLOW, 21); g.addEdge (BRAINTREE, WITHAM, 7); g.addEdge (CHELMSFORD, HARLOW, 17); g.addEdge (CHELMSFORD, RAYLEIGH, 13); g.addEdge (CHELMSFORD, SOUTHEND, 16); g.addEdge (CHELMSFORD, WITHAM, 9); g.addEdge (CLACTON, COLCHESTER, 13); g.addEdge (CLACTON, HARWICH, 10); g.addEdge (COLCHESTER, HARWICH, 17); g.addEdge (COLCHESTER, WITHAM, 14); g.addEdge (RAYLEIGH, SOUTHEND, 5);

   return g; } }