You should write a single program which implements Prim’s algorithm with different data structures, as well as the brute force search algorithm, to find the MST of an undirected, connected, weighted graph.
Program
Your program should read a symmetric matrix from a text file that describes weighted edges of an undirected, connected graph and find the MST that is saved in an output file as a sequence of edges of the MST. The program also displays the numbers of vertices and edges in the graph and the time spent to find its MST for each data structure used in Prim’s and the brute force search algorithms, which can be saved in another output file as well for your later analysis.
Your program should only measure the time spent by the algorithm with its data structure to find the MST so that it is a proper design to use one method/function to implement an algorithm and its associated data structure. For an algorithm that operates on a weight matrix, it takes the weight matrix stored in a two-dimensional array as its parameter; for an algorithm that operates on adjacency lists, it takes adjacency lists you created from the weight matrix. You may create your own list data structures based on arrays. No STL or Java Collection or other collection framework can be used. In the part of the algorithm implementation, you should not use any library functions including maximal or minimal functions but create your own functions to operate on arrays.
Your program should be readable and well commented.
In addition, you needs to create a small program or script to generate the weight matrix for a graph of various vertices and edges, saved to a text file. When you create graphs, you need consider the density and connectivity of graphs. You may use a program/script by other people, with reference to the source, to generate these matrices.
Data Structures and Algorithms
• Brute force search algorithm
The algorithm operates on a two-dimensional array that represents the weight matrix.
• Prim’s algorithm
The algorithm operates on one of the following data structures:
1. two-dimensional array that represents the weight matrix and unordered arrays;
2. adjacency lists and heaps.
