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**.

**Prim's in O(V^3)**

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?Prim();