How to implement Prim's MST algorithm efficiently with little code/using STL with C++?

Правка en2, от LunaticPriest, 2019-07-02 23:09:49

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?

Теги minimum heap, priority queue, c++

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский LunaticPriest 2019-07-02 23:09:49 0 (published)
en1 Английский LunaticPriest 2019-07-02 23:09:37 534 Initial revision (saved to drafts)