By bradyawn, history, 7 years ago,

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?

• +2

| Write comment?
 » 7 years ago, # |   0 C++ style pseudo code struct s { int total_cost,node,edge_cost; // total_cost represents total cost from originating node to the current node }; priority_queue Q; Q.push({0,0,0}); // 'node' value can be any valid node mst_cost = 0; while(!Q.empty()) { auto st = Q.top(); Q.pop(); if(visited[st.node]) continue; visited[st.node] = 1; mst_cost += st.edge_cost; // edge_cost is the cost of the edge we took to get to the current node for(child in adjency_list) if(!visited[child]) { Q.push({total_cost+(cost_of_edge_from_st.node_to_child),child,(cost_of_edge_from_st.node_to_child)}; } } //mst_cost has the cost of the minimum spanning tree 
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   +5 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).
 » 7 years ago, # |   +25 What about switching to one of the mentioned, faster algorithms?
 » 4 years ago, # | ← Rev. 4 →   0 Can anyone give me the link / suggestion / code on implementing Prim's MST using Priority Queue STL ?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Prim();int prim() { priority_queue > S; int res = 0; S.push({dis[1] = 0, 1}); while (!S.empty()) { int u = S.top().se; int du = S.top().fi; S.pop(); if (dis[u] != du) continue; res += dis[u]; dis[u] = 0; for (pi e : G[u]) { int v = e.fi, w = e.se; if (dis[v] > w) S.push({dis[v] = w, v}); } } return res; }