[Solved] Design and implement a program based on a greedy algorithm to solve the Minimal SpanningTree

C

Objectives?

Design and implement a program based on a greedy algorithm to solve the Minimal SpanningTree (MST) problem;?

Choose and implement appropriate data structures for the algorithm;? Analyse the efficiency of different implementations of the algorithm in comparison with thebrute force algorithm.TaskYou should write a single program which implements Prims 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 anundirected, connected graph and find the MST that is saved in an output file as a sequence of edges ofthe MST.

The program also displays the numbers of vertices and edges in the graph and the time spentto find its MST for each data structure used in Prims and the brute force search algorithms, which canbe 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 theMST so that it is a proper design to use one method/function to implement an algorithm and itsassociated data structure.

For an algorithm that operates on a weight matrix, it takes the weight matrixstored in a two-dimensional array as its parameter; for an algorithm that operates on adjacency lists, ittakes adjacency lists you created from the weight matrix.

You may create your own list data structuresbased on arrays. No STL or Java Collection or other collection framework can be used. In the part ofthe algorithm implementation, you should not use any library functions including maximal or minimalfunctions 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 ofvarious vertices and edges, saved to a text file.

When you create graphs, you need consider the densityand 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 algorithmThe algorithm operates on a two-dimensional array that represents the weight matrix.?

Prims algorithmThe 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.