Prims Algorithm using fibonnacci heap and Arraylist
- Problem description You are required to implement Prim’s Minimum Cost Spanning Tree algorithm, say MST, using a simple data structure, say simple scheme, as well as Fibonacci heap, say f-heap scheme, and measure the relative performance of the two implementations.
Both of the schemes MUST use the adjacency lists representation for graphs. The simple scheme uses an array to determine the next edge to include while the f-heap scheme uses a Fibonacci heap to do this. The simple scheme should run in O(n2) time, where n is the number of vertices in the graph.
- Input/Output Requirements Running modes: The name of your program should be mst.cpp for C++ and mst.java for Java. Your program MUST support all of the following modes.
(i) random mode: Run with graphs generated by random number generator. The command line for this mode is: $ mst –r n d // run in a random connected graph with n vertices and d% of density. // See Performance measurements section for details.
The following points should be noted in generating graphs in the random mode. Assume we have a function random(k) that returns a random integer in the range 0 to k-1. Also assume that the n vertices of a graph are labeled from 0 to n-1.
- To generate an edge set i = random(n), j = random(n) and cost = random(1000) + 1, and add the edge into the graph when edge (i, j) is not in the graph.
- After all edges are generated for a graph you need to make sure that the graph is connected. You can do this by running a depth-first search on the graph. Repeat the process of generating graphs until the graph is connected.
(ii) user input mode: In the user input mode, your program has to support redirected input from a file "file-name" which contains undirected graph representation. The command line for this mode is:
$mst -s file-name // read the input from a file ‘file-name’ for simple scheme $mst -f file-name // read the input from a file ‘file-name’ for f-heap scheme
In the user input mode, your program must get the following input format: n m // The number of vertices and edges respectively in the first line v1 v2 c1 // the edge (v1, v2) with cost c1 v2 v3 c2 // the edge (v2, v3) with cost c2 … // a total of m edges
Assume that vertices are labeled from 0 to n-1. An example input is shown below:
3 2
0 1 5
1 2 8
The graph consists of three vertices {0, 1, 2} and two edges (0,1) and (1,2) with costs 5 and 8 respectively.
In the user input mode, your program should display the cost of this tree in the first line and the edges in the constructed spanning tree in the following n-1 lines. Print the output to the standard output stream. The output for the example shown above is as follows:
13
0 1
1 2