Editing Prim's algorithm (section)

== Description ==
The algorithm may informally be described as performing the following steps:
{{ordered list
 |  Initialize a tree with a single vertex, chosen arbitrarily from the graph.
 | Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
 | Repeat step 2 (until all vertices are in the tree).
}}

In more detail, it may be implemented following the [[pseudocode]] below.
 '''function''' Prim(vertices, edges) '''is'''
     '''for''' '''each''' vertex '''in''' vertices '''do'''
         cheapestCost[vertex] ← ∞
         cheapestEdge[vertex] ← null
 
     explored ← empty set
     unexplored ← set containing all vertices
 
     startVertex ← any element of vertices
     cheapestCost[startVertex] ← 0
 
     '''while''' unexplored '''is''' not empty '''do'''
         // Select vertex in unexplored with minimum cost
         currentVertex ← vertex in unexplored with minimum cheapestCost[vertex]
         unexplored.remove(currentVertex)
         explored.add(currentVertex)
 
         '''for''' '''each''' edge (currentVertex, neighbor) '''in''' edges '''do'''
             '''if''' neighbor '''in''' unexplored '''and''' weight(currentVertex, neighbor) < cheapestCost[neighbor] THEN
                 cheapestCost[neighbor] ← weight(currentVertex, neighbor)
                 cheapestEdge[neighbor] ← (currentVertex, neighbor)
 
     resultEdges ← empty list
     '''for''' '''each''' vertex '''in''' vertices '''do'''
         '''if''' cheapestEdge[vertex] ≠ null '''THEN'''
             resultEdges.append(cheapestEdge[vertex])
 
     '''return''' resultEdges
As described above, the starting vertex for the algorithm will be chosen arbitrarily, because the first iteration of the main loop of the algorithm will have a set of vertices in ''Q'' that all have equal weights, and the algorithm will automatically start a new tree in ''F'' when it completes a spanning tree of each connected component of the input graph. The algorithm may be modified to start with any particular vertex ''s'' by setting ''C''[''s''] to be a number smaller than the other values of ''C'' (for instance, zero), and it may be modified to only find a single spanning tree rather than an entire spanning forest (matching more closely the informal description) by stopping whenever it encounters another vertex flagged as having no associated edge.

Different variations of the algorithm differ from each other in how the set ''Q'' is implemented: as a simple [[linked list]] or [[Array data structure|array]] of vertices, or as a more complicated [[priority queue]] data structure. This choice leads to differences in the [[time complexity]] of the algorithm. In general, a priority queue will be quicker at finding the vertex ''v'' with minimum cost, but will entail more expensive updates when the value of ''C''[''w''] changes.