Fill This Form To Receive Instant Help
Homework answers / question archive / CE204 Programming Assignment 2, 2021/22 Academic offences warning You may not use any libraries except for the standard Java runtime, i
CE204 Programming Assignment 2, 2021/22
You may not use any libraries except for the standard Java runtime, i.e., libraries that are imported using import java.[something]. The work that you submit must be your own. It is an academic offence to submit somebody else’s work as your own. This includes submitting code that you have downloaded from the internet and code that was produced in collaboration with another student, even if you have modified this code. You may study internet resources, textbooks, etc. but the code you submit must be written by you, not taken from or modified from these resources. For details, please consult the University’s guidance or ask me.
This assessed exercise constitutes 10% of your grade for CE204. 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.
Create a class called MST. Add a method static Graph getRandomGraph(int n) which creates 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.
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.)
Write a method static boolean isConnected (Graph g) which determines whether the given graph g is connected. Use breadth-first search – mark the vertices that have been
1
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.
You may use Java’s ConcurrentLinkedQueue<Integer> for the queue, for which you’ll need to import java.util.concurrent.*. Note that this class uses the name “poll” for the operation that I called remove in the lectures.
Write a method static void makeMST (Graph g) which replaces the graph g with its minimum spanning tree computed in the following way:
create a list of the graph’s 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 this class, please include its source in the file MST.java. You may use Java’s standard list classes, and you may use Collections.sort() to sort the list.
Add a main method to your class. It should perform the following tests.
Please submit only the file MST.java to Faser. Please do not submit a zip file. If you have written extra classes as part of your solution or used the Edge class, please include them in the same file as the main class. Please do not modify the MatrixGraph and GraphOfEssex classes, and please do not include those files in your submission.