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

CLICKHERE's blog

By CLICKHERE, history, 5 weeks ago, In English,

Is this Prim's MST Source Code is O(E logV) for dense graph? Notes: https://codeforces.com/blog/entry/68133?#comment-524560

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

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

    Which has the better time complexity between above and this

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

      Hint: Express E in terms of V in the worst case.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        I am not that great at CP, currently I am beginning at data structures. Please can you explain.

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

          $$$E=O(V^2)$$$ in the worst case

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

          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.

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

            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?