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

You do it like in Dijkstra's algorithm, by selecting the node that is connected to your current partial tree with the minimum cost edge (that doesn't generate a cycle). I think wikipedia explains Prim better than that pseudocode you have. Give it a look and let me know if you have more questions.

Answer 2

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)

Answer 3

You can sort the edges by the cost and then iterate the edges in the order of the cost, and if that edge joins two distinct subgraphs use that edge.

I have a implementation here. It reads the number of verticles (N), the number of edges (M) and the edges in order (A, B, Cost) and then outputs the edges. This is the Kruskal algorithm.

A implementation of the Prim's algorithm with a heap, using the same input can be found here.