Editing Prim's algorithm (section)

{{Short description|Method for finding minimum spanning trees}}
[[File:PrimAlgDemo.gif|200px|thumb|A demo for Prim's algorithm based on Euclidean distance]]

In [[computer science]], '''Prim's algorithm''' is a [[greedy algorithm]] that finds a [[minimum spanning tree]] for a [[Weighted graph|weighted]] [[undirected graph]]. This means it finds a subset of the [[edge (graph theory)|edge]]s that forms a [[Tree (graph theory)|tree]] that includes every [[Vertex (graph theory)|vertex]], where the total weight of all the [[graph theory|edges]] in the tree is minimized. The algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.

The algorithm was developed in 1930 by [[Czech people|Czech]] mathematician [[Vojtěch Jarník]]<ref>{{citation
 | last = Jarník | first = V. | author-link = Vojtěch Jarník
 | journal = Práce Moravské Přírodovědecké Společnosti
 | language = cs
 | volume = 6
 | issue = 4
 | pages = 57–63
 | title = O jistém problému minimálním
 |trans-title=About a certain minimal problem
 | year = 1930| hdl = 10338.dmlcz/500726 }}.</ref> and later rediscovered and republished by [[computer scientist]]s [[Robert C. Prim]] in 1957<ref>{{citation
 | title = Shortest connection networks And some generalizations
 | last = Prim | first = R. C. | author-link = Robert C. Prim
 | date = November 1957
 | journal = [[Bell System Technical Journal]]
 | volume = 36
 | issue = 6
 | pages = 1389–1401
 | doi = 10.1002/j.1538-7305.1957.tb01515.x
 | url = https://archive.org/details/bstj36-6-1389
| bibcode = 1957BSTJ...36.1389P }}.</ref> and [[Edsger W. Dijkstra]] in 1959.<ref>{{citation
 | last = Dijkstra | first = E. W. | author-link = Edsger W. Dijkstra
 | date = December 1959
 | journal = Numerische Mathematik
 | volume = 1
 | issue = 1
 | pages = 269–271
 | title = A note on two problems in connexion with graphs
 | url = http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf
 | doi = 10.1007/BF01386390
 | citeseerx = 10.1.1.165.7577
| s2cid = 123284777 }}.</ref> Therefore, it is also sometimes called the '''Jarník's algorithm''',<ref>{{citation
 | title=Algorithms
 | edition=4th
 | first1=Robert |last1=Sedgewick |author1-link=Robert Sedgewick (computer scientist)
 | first2=Kevin Daniel |last2=Wayne
 | publisher=Addison-Wesley
 | year=2011
 | page=628
 | isbn=978-0-321-57351-3
 | url=https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA628
}}.</ref> '''Prim–Jarník algorithm''',<ref>{{citation|title=Discrete Mathematics and Its Applications|edition=7th|first=Kenneth|last=Rosen|publisher=McGraw-Hill Science|year=2011|url=https://books.google.com/books?id=6EJOCAAAQBAJ&pg=PA798|page=798}}.</ref> '''Prim–Dijkstra algorithm'''<ref name="chertar">{{citation
 | last1 = Cheriton | first1 = David | author1-link = David Cheriton
 | last2 = Tarjan | first2 = Robert Endre | author2-link = Robert Tarjan
 | doi = 10.1137/0205051
 | issue = 4
 | journal = [[SIAM Journal on Computing]]
 | mr = 0446458
 | pages = 724–742
 | title = Finding minimum spanning trees
 | volume = 5
 | year = 1976}}.</ref>
or the '''DJP algorithm'''.<ref name="pr02">{{citation
 | title = An optimal minimum spanning tree algorithm
 | last1 = Pettie | first1 = Seth
 | last2 = Ramachandran | first2 = Vijaya | author2-link = Vijaya Ramachandran
 | date = January 2002
 | journal = Journal of the ACM
 | issue = 1
 | volume = 49
 | pages = 16–34
 | mr = 2148431
 | doi = 10.1145/505241.505243
 | citeseerx = 10.1.1.110.7670
 | s2cid = 5362916 | url = http://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf
}}.</ref>

Other well-known algorithms for this problem include [[Kruskal's algorithm]] and [[Borůvka's algorithm]].<ref>{{citation|first=Robert Endre|last=Tarjan|author-link=Robert Tarjan|title=Data Structures and Network Algorithms|series=CBMS-NSF Regional Conference Series in Applied Mathematics|volume=44|publisher=[[Society for Industrial and Applied Mathematics]]|year=1983|contribution=Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms|pages=72–77}}.</ref> These algorithms find the minimum spanning forest in a possibly disconnected graph; in contrast, the most basic form of Prim's algorithm only finds minimum spanning trees in connected graphs. However, running Prim's algorithm separately for each [[Connected component (graph theory)|connected component]] of the graph, it can also be used to find the minimum spanning forest.<ref>{{citation|title=Graph Algorithms in the Language of Linear Algebra|volume=22|series=Software, Environments, and Tools|first1=Jeremy|last1=Kepner|first2=John|last2=Gilbert|publisher=[[Society for Industrial and Applied Mathematics]]|year=2011|isbn=9780898719901|page=55|url=https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55}}.</ref> In terms of their asymptotic [[time complexity]], these three algorithms are equally fast for [[sparse graph]]s, but slower than other more sophisticated algorithms.<ref name="pr02"/><ref name="chertar"/>
However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in [[linear time]], meeting or improving the time bounds for other algorithms.<ref name="tarjan83p77">{{harvtxt|Tarjan|1983}}, p.&nbsp;77.</ref>

[[File:Prim's algorithm.svg|right|120px|thumb|Prim's algorithm starting at vertex A. In the third step, edges BD and AB both have weight 2, so BD is chosen arbitrarily. After that step, AB is no longer a candidate for addition to the tree because it links two nodes that are already in the tree.]]