December 6th, 2011, 05:08 AM
Algorithms...do you know their taste?
I was studying algorithms from Cormen recently. I read the topic "Minimum spanning trees". I was wondering what is the exact difference between the Generic Minimum Spanning Tree algorithm and Prim's Spanning tree Algorithm.
What I think is both function exactly same way. Prim has just given pseudo-code to implement generic algorithm. Nothing more...
I surfed the net also but could not find the relevant information. Got to know many things like Prim,Loberman, Weinberger, and Dijkstra all designed algorithm around same time.
But then why the heck Prim's algorithm is so famous? I think I kinda know answer to this question. Its running time for graph G(V,E) is of O(E+VlnV) by Fibonacci heaps and it can be reduced further.
Just want to make sure through this forum and please, please answer my 1st question:
What is the exact difference between the generic MST algo and Prim's MST algo. Corect me if my thinking is wrong and functioning of both is different.