Prim’s and Kruskal’s Algorithms: An Analysis
The actual emperical graphs were a bit wonky if you look, I need to spend more time on gnuplot to figure out how to fix this. I would want to run more comparisons between algorithm to verify them. This could be done with graphs with different densities with relative ease as the number of 0’s in the matrices used can easily be changed. Furthermore, I would like to implement Neeraj Mishra’s (thecrazyprogrammer.com) and fedelebron’s (fedelebron.com) code of Kruskal’s and Prim’s algorithm on my program for working out the runtime of the algorithm and plotting this in Gnuplot. This is empected to yield more accurate results. Another area of interest would be to investigate the possible minimum spanning forest case in Kruskal’s algorithm.
Enjoy the research report I created for this assignment below! This will give the the technical details such as the asymptotic growth of each algorithm and which algorithm works best for dense graphs.
And if you have read this far, here is your reward (the original PDF!):
Jonathan_Taylor_1665909_COMS2004_Assignment_Q7