Algoritmo de Prim - Historial de revisiones

Yunesky jc.mtz en 14:44 10 jun 2013

2013-06-10T14:44:23Z

Midel: /* Referencias */

2012-01-19T19:12:54Z

‎Referencias

Editor oni en 21:06 2 jul 2010

2010-07-02T21:06:37Z

Asanto uci: Página creada con '{{Referencia}}
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 …'

2010-07-02T18:19:02Z

Página creada con '{{Referencia}} 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 …'

Página nueva

{{Referencia}} 

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.

== Descripción conceptual ==

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

== Pseudocódigo del algoritmo ==

*Estructura de datos auxiliar: Q = [[Estructura de datos]] '''[[Cola de prioridad]]''' (se puede implementar con un [[Montículo (programación)|heap]])

'''JARNIK''' (Grafo ''G'', nodo_fuente ''s'')

''// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL''
''// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas <nodo,distancia> del grafo''
'''por cada''' ''u'' en ''V[G]'' '''hacer'''
distancia[''u''] = INFINITO
padre[''u''] = NULL
Añadir(cola,<''u'',distancia[''u'']>)
distancia[''s'']=0
'''mientras''' cola != 0 '''do'''
''// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.''
''u'' = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.
'''por cada''' '''v''' adyacente a ''''u'''' '''hacer'''
'''si''' ((''v'' ∈ cola) '''&&''' (distancia[''v''] > peso(u, v)) '''entonces'''
padre[''v''] = ''u''
distancia[''v''] = peso(u, v)
Actualizar(cola,<''v'',distancia[''v'']>)

== Código en JAVA ==
<pre>public class Algorithms
{
public static Graph PrimsAlgorithm (Graph g, int s)
{
int n = g.getNumberOfVertices ();
Entry[] table = new Entry [n];
for (int v = 0; v < n; ++v)
table [v] = new Entry ();
table [s].distance = 0;
PriorityQueue queue =
new BinaryHeap (g.getNumberOfEdges());
queue.enqueue (
new Association (new Int (0), g.getVertex (s)));
while (!queue.isEmpty ())
{
Association assoc = (Association) queue.dequeueMin();
Vertex v0 = (Vertex) assoc.getValue ();
int n0 = v0.getNumber ();
if (!table [n0].known)
{
table [n0].known = true;
Enumeration p = v0.getEmanatingEdges ();
while (p.hasMoreElements ())
{
Edge edge = (Edge) p.nextElement ();
Vertex v1 = edge.getMate (v0);
int n1 = v1.getNumber ();
Int wt = (Int) edge.getWeight ();
int d = wt.intValue ();
if (!table[n1].known && table[n1].distance>d)
{ table [n1].distance = d;
table [n1].predecessor = n0;
queue.enqueue (
new Association (new Int (d), v1));
}
}
}
}
Graph result = new GraphAsLists (n);
for (int v = 0; v < n; ++v)
result.addVertex (v);
for (int v = 0; v < n; ++v)
if (v != s)
result.addEdge (v, table [v].predecessor);
return result;
}
}

</pre>
== Demostración ==

Sea G un grafo [[Teoría de los grafos#Grafos_Conexos|conexo]] y [[Teoría de los grafos#Grafos_ponderados|ponderado]].

 

Ya que G es conexo, siempre habrá un camino para todo nodo.

La salida Y del algoritmo de Prim es un árbol porque las aristas y los nodos agregados a Y están conectados.

Sea Y el árbol recubridor mínimo de G.

Si Y1=Y es el árbol recubridor mínimo.

Si no, sea la primera arista agregada durante la construcción de Y, que no está en Y1 y sea V el conjunto de nodos conectados por las aristas agregadas antes que ''e''. Entonces un extremo de V está en V y el otro no. Ya que Y1 es el árbol recubridor mínimo de G hay un camino en Y1 que une los dos extremos. Mientras que uno se mueve por el camino, se debe encontrar una arista ''f'' uniendo un nodo en V a uno que no está en V. En la iteración que ''e'' se agrega a Y, ''f'' también se podría haber agregado y se hubiese agregado en vez de ''e'' si su peso fuera menor que el de ''e''. Ya que ''f'' no se agregó se concluye:

:Sea Y2 el grafo obtenido al remover f y agregando e \in Y_1. Es fácil mostrar que Y2 conexo tiene la misma cantidad de aristas que Y1, y el peso total de sus aristas no es mayor que el de Y1, entonces también es un árbol recubridor mínimo de G y contiene a e y todas las aristas agregadas anteriormente durante la construcción de V. Si se repiten los pasos mencionados anteriormente, eventualmente se obtendrá el árbol recubridor mínimo de G que es igual a Y.

Esto demuestra que Y es el árbol recubridor mínimo de G.

 

== Referencias ==

*R. C. Prim: ''Shortest connection networks and some generalisations''. In: ''Bell System Technical Journal'', 36 (1957), pp. 1389–1401
*D. Cherition and R. E. Tarjan: ''Finding minimum spanning trees''. In: ''SIAM Journal of Computing'', 5 (Dec. 1976), pp. 724–741
*[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.

 

[[Category:Algoritmos]]

← Revisión anterior		Revisión del 14:44 10 jun 2013
Línea 1:		Línea 1:
−	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.	+	{{Definición\|Nombre=Algoritmo de Prim\|imagen=\|concepto=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.}}
		+
		+	'''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.		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.

@@ Línea 1: / Línea 1: @@
-{{Referencia}}<br>
+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.
+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.
 == Descripción conceptual  ==

@@ Línea 104: / Línea 104: @@
 <br>
 == Referencias  ==
 *R. C. Prim: ''Shortest connection networks and some generalisations''. In: ''Bell System Technical Journal'', 36 (1957), pp. 1389–1401
 *D. Cherition and R. E. Tarjan: ''Finding minimum spanning trees''. In: ''SIAM Journal of Computing'', 5 (Dec. 1976), pp. 724–741
 *[[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
 [[Category:Algoritmos]]

Algoritmo de Prim - Historial de revisiones

Yunesky jc.mtz en 14:44 10 jun 2013

Midel: /* Referencias */

Editor oni en 21:06 2 jul 2010

Asanto uci: Página creada con '{{Referencia}} 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 …'

Asanto uci: Página creada con '{{Referencia}}
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 …'