Prim's algorithm

Prim's algorithm for finding a minimum spanning tree is based on a priority queue. You start with a single node and construct the tree. For each node not already in the tree, you keep track of the minimum weighted edge betwee it and the tree (if any). You pick the node with the smallest such weight, and update the values. This greedy algorithm produces the minimum spanning tree.

In Pseudocode:

1. Pick a random vertex and insert it into the queue with a priority of 0.
2. Remove the vertex from the priority queue with the smallest priority. Call that vertex v.
3. For all neighbors of v which have not ever been removed from the priority queue before:
   • If it's not in the priority queue, add it to the priority queue with a priority equal to the weight of the edge between v and it.
   • If it's already in the priority queue, ensure that it's priority is no greater than the weight of the edge between v and it. If it's current priority is higher, update it to the new value.
4. If the priority queue is empty, stop. Otherwise, go to step 2.