Growing one tree outward
Starting from any vertex of a connected undirected weighted graph, Prim selects a lightest edge crossing between tree vertices and outside vertices, bringing one more vertex into the tree each time.
An eligible edge must cross the current boundary. An edge wholly inside creates a cycle rather than adding a vertex; one wholly outside does not extend the current tree. Being globally cheap is not enough to make an edge the next candidate.
References: [1]
Lazy edge queues and eager updates
A lazy implementation queues edges from each newly added vertex to outside vertices. Some become internal as the tree grows; they remain queued until removal, when they are recognized and skipped.
An eager implementation retains only each candidate outside vertex’s best connecting edge. Newly scanned edges can lower that vertex’s priority, requiring an indexed priority queue capable of locating and updating the corresponding entry.
References: [1]
Implementation costs differ from shortest-path rules
On connected input, a usual lazy binary-heap version takes O(E log E) time and O(E) extra space; an indexed eager version takes O(E log V) time and O(V) space, excluding the graph. They implement the same safe-edge principle with different queue contents. General disconnected input also requires visiting and initializing all V vertices; lazy-version storage includes that vertex state and is O(V+E), even when many vertices are isolated.
Negative weights are permitted, unlike standard Dijkstra shortest-path assumptions. On disconnected input, growth must restart in other components to produce a minimum spanning forest; one local run cannot cross a nonexistent connection.