Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### CLICKHERE's blog

By CLICKHERE, history, 5 weeks ago, , Is this Prim's MST Source Code is O(E logV) for dense graph? Notes: https://codeforces.com/blog/entry/68133?#comment-524560 Comments (11)
 » Of course. But, that is guaranteed for Prim's MST algorithm when using a priority queue.But you can do better by using an array instead in the case of dense graphs.
•  » » Which has the better time complexity between above and this
•  » » » Hint: Express E in terms of V in the worst case.
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   I am not that great at CP, currently I am beginning at data structures. Please can you explain.
•  » » » » »
•  » » » » » $E=O(V^2)$ in the worst case
•  » » » » » On dense graphs, $E \in O(V^2)$. So if you use priority queue, the time complexity is $\mathcal{O}(V^2\log V)$.If you use the adjacency matrix method instead, you would have $\mathcal{O}(V^2)$ instead.
•  » » » » » » if the question constraint using prim's mst only then on dense graph I shall use matrix method and on sparse I shall use priority queue method?
•  » » » » » » » And Thankyou for the help
•  » » » » » » » Actually, on sparse graphs, you are better off using kruskal's MST algo.
•  » » » » » » » » Okay