Metraipolis › archive › dc_7f5ddcc6fcc0
Prim's algorithm — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Prim%27s_algorithm
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T14:06:20.037Z
- SHA-256 of the archived text
4ab14aae835f3a3ccb65528f44939c0ac27d209f9920206be0cdfe15a7163c85- Stable URL of this page
https://metraipolis.com/documento/dc_7f5ddcc6fcc0
How to cite
Prim's algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Prim%27s_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7f5ddcc6fcc0 (Metraipolis archive dc_7f5ddcc6fcc0, sha256 4ab14aae835f3a3ccb65528f44939c0ac27d209f9920206be0cdfe15a7163c85)
BibTeX
@misc{dc7f5ddcc6fcc0,
title = {Prim's algorithm — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Prim%27s_algorithm},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7f5ddcc6fcc0; sha256 4ab14aae835f3a3ccb65528f44939c0ac27d209f9920206be0cdfe15a7163c85},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Prim%27s_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»). Fonte: Wikipedia in inglese, voce «Prim's algorithm» — https://en.wikipedia.org/wiki/Prim%27s_algorithm Wikidata Q470813: «algoritmo sui grafi» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q470813 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Prim%27s_algorithm?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1368985795, consultata il 2026-10-06T12:26:06.716Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4723f0a7b3c0ea757b7250b1452d6aa202287818a1b6b1c0d08483874fb6e10a