Prim's algorithm computes a minimum spanning tree when edges have
Prim's algorithm works by doing a sort of breadth-first search, starting
from some arbitrary node, and keeping the edges in a priority queue. It
keeps extracting the lowest-weight edge and either discarding it without
expanding the search (if the edge leads to a node already in the tree) or
adding it to the result, marking its opposite node as in the tree, and
expanding the search.
Done in the naive way I just explained, Prim's algorithm is dominated by
the cost of enqueueing and dequeueing
|E| edges into/outof the
priority queue. Each enqueue/dequeue takes
O(log |E|) time, so
the total asymptotic cost is
O(|E| log |E|) time or, more
O(|E| log |E| + |V|).
If we had some way to do those enqueues and dequeues in constant time,
the total running time would be
O(|E| + |V|)...