My implementation of Prim's is really slow.
So I searched up a fast way to do Prim's algorithm on geeksforgeeks.com, it is here: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-minimum-spanning-tree-mst-2/ It is O(V^2). It uses two disjoint sets and finds the minimum edges between them with an adjacency matrix.
But the website has a faster way: http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/ It is O(ElogV). It uses an adjacency list and a priority_queue to speed up Prim's.
I understand the concept of Prim's, but my implementation is really slow.
It is O(V^3).
Here is the problem it applies to (very straight forward): http://www.spoj.com/problems/MST/ — I got AC my but my algorithm is very slow
How can I improve this implementation?
Hello, I wrote the solution at you proposed in O(V^2). When will this be better than an O(ElogE) Kruskal's implementation?
Can we further speed this up?
Kruskal is faster when you have sparse graphs (graphs with a low number of edges), and Prim's will be faster in dense graphs (lots of edges). However notice, you will only get the full potential for Prim's alg, if you use a Fibonacci heap. Using it you will have a runtime of O(E + V logV).
What about switching to one of the mentioned, faster algorithms?
Can anyone give me the link / suggestion / code on implementing Prim's MST using Priority Queue STL ?