Java – how complex is the prims algorithm using priority queues?

I use adjacency matrix and priority queue is data structure

According to my calculation, the complexity is v ^ 3 log V:

>While loop: V > check adjacent vertices: V > if the entry already exists, check the queue and update the same content: V log V

But I read everywhere that complexity is v ^ 2

Please explain

Solution

If you use Fibonacci heap, extract min as O (LG V) amortization cost and update the entry as O (1) amortization

If we use this pseudo code

while priorityQueue not empty
    u = priorityQueue.exractMin()
    for each v in u.adjacencies
        if priorityQueue.contains(v) and needsWeightReduction(u,v)
            priorityQueue.updateKeyWeight(u,v)

Suppose the implementation has PriorityQueue Constant time of contains (V) and needsweightreduction (U, V)

It should be noted that you can slightly strengthen the inspection of adjacency Although the outer loop runs V times and checking the adjacency of any single node is the worst V operation, you can use aggregation analysis to realize that you will never check more than e adjacency (because there are only e edges) And e < = V ^ 2, so this is a slightly better boundary So, you have external circulation V times and internal circulation e times Extract min runs V times, and update entries in the heap runs e times

V*lgV + E*1
= O(V lgV + E)

Similarly, since e < = V ^ 2, you can replace and get this fact

O(V lgV + V^2)
= O(V^2)

But when considering sparse graphs, this is a looser bound (though correct)