Algoritmo de Prim
Sign in to saveAlso known as DJP algorithm, Jarník algorithm, Prim–Jarník algorithm, Prim–Dijkstra algorithm, Jarnik algorithm
algorithm for finding the minimum spanning tree for weighted undirected graphs
Wikidata facts
- Instance of
- algorithm
- Named after
- Vojtěch Jarník
- Has use
- decision tree
Show 2 more facts
- Commons category
- Prim's algorithm
- discoverer or inventor
- Edsger W. Dijkstra
Sources (2)
via Wikidata · CC0
Article · Español
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo. El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.
Abstract from DBpedia / Wikipedia · CC BY-SA