Editing Prim's algorithm (section)

== Time complexity ==
[[File:MAZE 30x20 Prim.ogv|thumb|Prim's algorithm has many applications, such as in the [[maze generation|generation]] of this maze, which applies Prim's algorithm to a randomly weighted [[grid graph]].]]

The time complexity of Prim's algorithm depends on the data structures used for the graph and for ordering the edges by weight, which can be done using a [[priority queue]]. The following table shows the typical choices:

{| class="wikitable"
! Minimum edge weight data structure !! Time complexity (total)
|-
| [[adjacency matrix]], searching || <math>O(|V|^2)</math>
|-
| [[binary heap]] and [[adjacency list]] || <math>O((|V| + |E|) \log |V|) = O(|E| \log |V|)</math>
|-
| [[Fibonacci heap]] and [[adjacency list]] || <math>O(|E| + |V| \log |V|)</math>
|}

A simple implementation of Prim's, using an [[adjacency matrix]] or an [[adjacency list]] graph representation and linearly searching an array of weights to find the minimum weight edge to add, requires [[Big-O notation|O]](<nowiki>|</nowiki>V<nowiki>|</nowiki><sup>2</sup>) running time. However, this running time can be greatly improved by using [[Heap (data structure)|heaps]] to implement finding minimum weight edges in the algorithm's inner loop.

A first improved version uses a heap to store all edges of the input graph, ordered by their weight. This leads to an O(|E| log |E|) worst-case running time. But storing vertices instead of edges can improve it still further. The heap should order the vertices by the smallest edge-weight that connects them to any vertex in the partially constructed [[minimum spanning tree]] (MST) (or infinity if no such edge exists). Every time a vertex ''v'' is chosen and added to the MST, a decrease-key operation is performed on all vertices ''w'' outside the partial MST such that ''v'' is connected to ''w'', setting the key to the minimum of its previous value and the edge cost of (''v'',''w'').

Using a simple [[binary heap]] data structure, Prim's algorithm can now be shown to run in time [[Big-O notation|O]](<nowiki>|</nowiki>E<nowiki>|</nowiki> log <nowiki>|</nowiki>V<nowiki>|</nowiki>) where <nowiki>|</nowiki>E<nowiki>|</nowiki> is the number of edges and <nowiki>|</nowiki>V<nowiki>|</nowiki> is the number of vertices. Using a more sophisticated [[Fibonacci heap]], this can be brought down to [[Big-O notation|O]](<nowiki>|</nowiki>E<nowiki>|</nowiki> + <nowiki>|</nowiki>V<nowiki>|</nowiki> log <nowiki>|</nowiki>V<nowiki>|</nowiki>), which is [[Asymptotic computational complexity|asymptotically faster]] when the graph is [[Dense graph|dense]] enough that <nowiki>|</nowiki>E<nowiki>|</nowiki> is [[Big-O notation#Family of Bachmann.E2.80.93Landau notations|ω]](<nowiki>|</nowiki>V<nowiki>|</nowiki>), and [[linear time]] when |E| is at least |V|&nbsp;log&nbsp;|V|. For graphs of even greater density (having at least |V|<sup>''c''</sup> edges for some ''c''&nbsp;>&nbsp;1), Prim's algorithm can be made to run in linear time even more simply, by using a [[d-ary heap|''d''-ary heap]] in place of a Fibonacci heap.<ref name="tarjan83p77"/><ref>{{citation
 | last = Johnson | first = Donald B. | author-link = Donald B. Johnson
 | date = December 1975
 | doi = 10.1016/0020-0190(75)90001-0
 | issue = 3
 | journal = Information Processing Letters
 | pages = 53–57
 | title = Priority queues with update and finding minimum spanning trees
 | volume = 4}}.</ref>

[[File:Prim's algorithm proof.svg|thumb|150px|Demonstration of proof. In this case, the graph ''Y<sub>1</sub>'' = ''Y'' − ''f'' + ''e'' is already equal to ''Y''. In general, the process may need to be repeated.]]