Prim's algorithm
≈ 5 min read
Names in other languages
- EnglishPrim's algorithm
- PolskiAlgorytm Prima
- 한국어프림 알고리즘
- 中文普里姆算法
- 简体中文普里姆算法
- 繁體中文普林演算法
- 中文普林演算法
- 中文普里姆算法
- 中文普林演算法
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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 and later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959. Therefore, it is also sometimes called Jarník's algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm or the DJP algorithm. Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. 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. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms.…
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 and later rediscovered and republished by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959. Therefore, it is also sometimes called Jarník's algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm or the DJP algorithm. Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm. 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. In terms of their asymptotic time complexity, these three algorithms are equally fast for sparse graphs, but slower than other more sophisticated algorithms. 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. Let Y 1 be a minimum spanning tree of graph P. If Y 1 =Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of tree Y that is not in tree Y 1 , and V be the set of vertices connected by the edges added before edge e. Then one endpoint of edge e is in set V and the other is not. Since tree Y 1 is a spanning tree of graph P, there is a path in tree Y 1 joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in set V to one that is not in set V. Now, at the iteration when edge e was added to tree Y, edge f could also have been added and it would be added instead of edge e if its weight was less than e, and since edge f was not added, we conclude that w(f) \ge w(e). Let tree Y 2 be the graph obtained by removing edge f from and adding edge e to tree Y 1 . It is easy to show that tree Y 2 is connected, has the same number of edges as tree Y 1 , and the total weights of its edges is not larger than that of tree Y 1 , therefore it is also a minimum spanning tree of graph P and it contains edge e and all the edges added before it during the construction of set V. Repeat the steps above and we will eventually obtain a minimum spanning tree of graph P that is identical to tree Y. This shows Y is a minimum spanning tree. The minimum spanning tree allows for the first subset of the sub-region to be expanded into a larger subset X, which we assume to be the minimum.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1368985795 under CC BY-SA 4.0; modifications have been made.