Back خوارزمية بريم Arabic Algorisme de Prim Catalan Jarníkův algoritmus Czech Algorithmus von Prim German Algoritmo de Prim Spanish الگوریتم پریم Persian Algorithme de Prim French האלגוריתם של פרים HE Prim-algoritmus Hungarian Algoritma Prim ID

Prim's algorithm

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 undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the 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 mathematician Vojtěch Jarník[1] and later rediscovered and republished by computer scientists Robert C. Prim in 1957[2] and Edsger W. Dijkstra in 1959.[3] Therefore, it is also sometimes called the Jarník's algorithm,[4] Prim–Jarník algorithm,[5] Prim–Dijkstra algorithm[6] or the DJP algorithm.[7]

Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm.[8] 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 of the graph, it can also be used to find the minimum spanning forest.[9] In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms.[7][6] 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.[10]

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.
  1. ^ Jarník, V. (1930), "O jistém problému minimálním" [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti (in Czech), 6 (4): 57–63, hdl:10338.dmlcz/500726.
  2. ^ Prim, R. C. (November 1957), "Shortest connection networks And some generalizations", Bell System Technical Journal, 36 (6): 1389–1401, Bibcode:1957BSTJ...36.1389P, doi:10.1002/j.1538-7305.1957.tb01515.x.
  3. ^ Dijkstra, E. W. (December 1959), "A note on two problems in connexion with graphs" (PDF), Numerische Mathematik, 1 (1): 269–271, CiteSeerX 10.1.1.165.7577, doi:10.1007/BF01386390, S2CID 123284777.
  4. ^ Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms (4th ed.), Addison-Wesley, p. 628, ISBN 978-0-321-57351-3.
  5. ^ Rosen, Kenneth (2011), Discrete Mathematics and Its Applications (7th ed.), McGraw-Hill Science, p. 798.
  6. ^ a b Cheriton, David; Tarjan, Robert Endre (1976), "Finding minimum spanning trees", SIAM Journal on Computing, 5 (4): 724–742, doi:10.1137/0205051, MR 0446458.
  7. ^ a b Pettie, Seth; Ramachandran, Vijaya (January 2002), "An optimal minimum spanning tree algorithm" (PDF), Journal of the ACM, 49 (1): 16–34, CiteSeerX 10.1.1.110.7670, doi:10.1145/505241.505243, MR 2148431, S2CID 5362916.
  8. ^ Tarjan, Robert Endre (1983), "Chapter 6. Minimum spanning trees. 6.2. Three classical algorithms", Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 44, Society for Industrial and Applied Mathematics, pp. 72–77.
  9. ^ Kepner, Jeremy; Gilbert, John (2011), Graph Algorithms in the Language of Linear Algebra, Software, Environments, and Tools, vol. 22, Society for Industrial and Applied Mathematics, p. 55, ISBN 9780898719901.
  10. ^ Tarjan (1983), p. 77.

Rich TVX News Network Site

Rich TVX News Network Info

© MMXXIII Rich X Search. We shall prevail. All rights reserved. Rich X Search