This Python program uses Prim's Algorithm to build a minimum spanning tree out of a collection of points in a Cartesian plane.
A priority queue, in particular a binary min heap, is filled with the nodes. The min heap uses cost as the key. The initial cost of all nodes is negative infinity. An arbitrarily picked node is updated with a cost of 0. A set of unvisited nodes is populated with all nodes. A while loop is performed until the priority queue is empty of unvisited nodes. The minimum cost node is extracted from the min heap. The cost of the extracted node is the final cost. The extracted node is also removed from the set of unvisited nodes. The edge cost - from the extracted node to every unvisited node - is calculated as the distance from the extracted node in the Cartesian plane. If the edge cost is lower than the cost of an unvisited node, then the cost of the unvisited node is updated. This updated cost of the unvisited node is updated in the priority queue. A simple way to update the key of nodes in the priority queue is to enter another instance of the same node but with a lowered cost. Only the first instance of a node that is extracted form the priority queue is used. Other higher cost instances are not used upon extraction from the priority, since a check of the set of unvisited nodes will not include the node. When the priority queue is empty of unvisited nodes, the while loop is over.