LunaticPriest's blog

How to implement Prim's MST algorithm efficiently with little code/using STL with C++?
By LunaticPriest, history, 5 years ago, In English

Prim's algorithm requires a binary heap. At first, I thought I could easily use a priority queue, but it turns out that I have to reduce the weights of vertices in the priority queue, but it takes O(n) to find the vertex and modify its weight. A min-heap has the ability to reduce the weights of the vertices but it takes a lot of time to code it up, so it isn't useful for competitions. How to reduce the weight of the vertex with less complexity?

  • Vote: I like it
  • -5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you want a min heap, just use priority_queue<int, vector<int>, greater<int> > pq; instead of just priority_queue<int> pq

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

    Yes, I am aware of that method, what I'm actually concerned about is the complexity of finding the vertex and changing its weight.

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

      Couldn't you just change the weight and rerun Prim for O(n lg n)?

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

        If each weight change costs me O(n), in the worst case I believe it will change a weight number of edges times, so the complexity becomes something like O(V*E) which can also be O(V^3), but the algorithm should be O(nlogn).

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

Why do you have to reduce the weight of edges in the priority queue?

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

On an unrelated note, why are you trying to implement Prim's algorithm? For homework? For practice? If you do not need to do it for official reasons, I suggest that you use kruskal's algo instead. It is much much easier than prim's algo and is better suited for programming contests.

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

    I think prim has some applications with counting number of trees in some problems (this is just a vague memory, so I can't provide details).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You have several options:

  1. Instead of changing the weight of the vertex insert several copies of the same vertex on the priority queue (PQ). Each vertex will be inserted in the PQ at most its degree, hence you will need to push/pop $$$O(E)$$$ times from the PQ. (Note if you do this you will only process each vertex once, the first time). Now the complexity will be $$$O(E \log E)$$$ but since $$$E$$$ is at most $$$V^2$$$ we got same complexity $$$O(E \log V)$$$. (This is not the best complexity you can achieve using Prim).

  2. Use a set instead of a PQ. When you want to modify an element just delete it and insert the modified value again. Time complexity is the same using set and PQ, but PQ is significantly faster and you should prefer it if you have that option.

  3. Use Kruskal instead.

I find Kruskal easier to implement as pointed by LanceTheDragonTrainer, I only implement Prim when the graph is dense, and instead of using a PQ you can use and array. Updates and finding minimum is done in linear time. Overall complexity is $$$O(V^2)$$$ and code is even simpler than Kruskal.

→ Reply