bradyawn's blog

How to speed up Prim's Algorithm?
By bradyawn, history, 6 years ago, In English

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?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
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
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

What about switching to one of the mentioned, faster algorithms?

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone give me the link / suggestion / code on implementing Prim's MST using Priority Queue STL ?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Prim();
    → Reply