Блог пользователя bradyawn

How to speed up Prim's Algorithm?
Автор bradyawn, история, 7 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 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 лет назад, # ^ |
      Проголосовать: нравится 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 лет назад, # ^ |
        Проголосовать: нравится +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 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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

→ Ответить
»
5 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Prim();
    → Ответить