Editing Prim's algorithm (section)

== Parallel algorithm ==
[[File:Distributed adjacency matrix for parallel prim.png|thumb|The adjacency matrix distributed between multiple processors for parallel Prim's algorithm. In each iteration of the algorithm, every processor updates its part of ''C'' by inspecting the row of the newly inserted vertex in its set of columns in the adjacency matrix. The results are then collected and the next vertex to include in the MST is selected globally.]]

The main loop of Prim's algorithm is inherently sequential and thus not [[parallel algorithm|parallelizable]]. However, the [[#step3c|inner loop]], which determines the next edge of minimum weight that does not form a cycle, can be parallelized by dividing the vertices and edges between the available processors.<ref name="grama2003">{{citation|title=Introduction to Parallel Computing|last1=Grama|first1=Ananth|last2=Gupta|first2=Anshul|last3=Karypis|first3=George|last4=Kumar|first4=Vipin|year=2003|isbn=978-0201648652|pages=444–446|publisher=Addison-Wesley }}</ref> The following [[pseudocode]] demonstrates this.

{{ordered list
  | Assign each processor <math>P_i</math> a set <math>V_i</math> of consecutive vertices of length <math>\tfrac{|V|}{|P|}</math>.
  | Create C, E, F, and Q as in the [[#sequential_algorithm|sequential algorithm]] and divide C, E, as well as the graph between all processors such that each processor holds the incoming edges to its set of vertices. Let <math>C_i</math>, <math>E_i</math> denote the parts of ''C'', ''E'' stored on processor <math>P_i</math>.
  | Repeat the following steps until ''Q'' is empty:
{{ordered list|type=a
  | On every processor: find the vertex <math>v_i</math> having the minimum value in <math>C_i</math>[<math>v_i</math>] (local solution).
  | [[Reduction Operator|Min-reduce]] the local solutions to find the vertex ''v'' having the minimum possible value of ''C''[''v''] (global solution).
  | [[Broadcasting (computing)|Broadcast]] the selected node to every processor.
  | Add ''v'' to ''F'' and, if ''E''[''v''] is not the special flag value, also add ''E''[''v''] to ''F''.
  | On every processor: update <math>C_i</math> and <math>E_i</math> as in the sequential algorithm.
}} 
 | Return ''F''
}}

This algorithm can generally be implemented on distributed machines<ref name="grama2003" /> as well as on shared memory machines.<ref>{{citation|last1=Quinn|first1=Michael J.|last2=Deo|first2=Narsingh|date=1984|title=Parallel graph algorithms|journal=ACM Computing Surveys |volume=16 |issue=3|pages=319–348|doi=10.1145/2514.2515|s2cid=6833839|doi-access=free}}</ref> The running time is <math>O(\tfrac{|V|^2}{|P|}) + O(|V| \log |P|)</math>, assuming that the ''reduce'' and ''broadcast'' operations can be performed in <math>O(\log |P|)</math>.<ref name="grama2003" /> A variant of Prim's algorithm for shared memory machines, in which Prim's sequential algorithm is being run in parallel, starting from different vertices, has also been explored.<ref>{{citation|last=Setia|first=Rohit|date=2009|title=A new parallel algorithm for minimum spanning tree problem|journal=Proc. International Conference on High Performance Computing (HiPC)|url=https://ncit-cluster.grid.pub.ro/trac/PP2009/export/157/proiecte/pgraph/Documentation/parallelspannintree.pdf}}</ref> It should, however, be noted that more sophisticated algorithms exist to solve the [[distributed minimum spanning tree]] problem in a more efficient manner.