Prim's MST algorithm in O(|V|^2)

Question

Time complexity of Prim's MST algorithm is O(|V|^2) if you use adjacency matrix representation.

I am trying to implement Prim's algorithm using adjacency matrix. I am using this as a reference.

V = {1,2...,n}
U = {1}
T = NULL
while V != U:

     /* 
         Now this implementation means that 
         I find lowest cost edge in O(n).
         How do I do that using adjacency list? 
     */

     let (u, v) be the lowest cost edge 
                such that u is in U and v is in V - U;

     T = T + {(u,v)}
     U = U + {v}

EDIT:

1. I understand Prim's algorithm very well.
2. I know how to implement it efficiently using heaps and priority queues.
3. I also know about better algorithms.
4. I want to use adjacency matrix representation of graph and get O(|V|^2) implementation.

I WANT THE INEFFICIENT IMPLEMENTATION

Answer 1

Finding the lowest cost edge (u,v), such that u is in U and v is in V-U, is done with a priority queue. More precisely, the priority queue contains each node v from V-U together with the lowest cost edge from v into the current tree U. In other words, the queue contains exactly |V-U| elements.

After adding a new node u to U, you have to update the priority queue by checking whether the neighboring nodes of u can now be reached by an edge of lower cost than previously.

The choice of priority queue determines the time complexity. You will get O(|V|^2) by implementing the priority queue as a simply array cheapest_edges[1..|V|]. That's because finding minimum in this queue takes O(|V|) time, and you repeat that |V| times.

In pseudo-code:

V = {2...,n}
U = {1}
T = NULL
P = array, for each v set P[v] = (1,v)

while V != U

    (u,v) = P[v] with v such that  length P[v]  is minimal

    T = T + {(u,v)}
    U = U + {v}

    for each w adjacent to v
        if length (v,w) < length P[w] then
            P[w] = (v,w)