Ir al contenido

Diferencia entre revisiones de «Algoritmo de Prim»

De Wikipedia, la enciclopedia libre
Contenido eliminado Contenido añadido
m Revertidos los cambios de 200.48.7.17 a la última edición de DumZiBoT
Línea 6: Línea 6:
== Descripción conceptual==
== 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 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.
El árbol recubridor mínimo está completamente construido cuando no quedan más vértices por agregar.

Revisión del 19:33 26 may 2009

El algoritmo de Prim es un algoritmo de 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

   PRIM (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
       for each uV[G] do
           distancia[u] = INFINITO
           padre[u] = NULL
       distancia[s]=0
       //encolamos todos los nodos del grafo
       Encolar(cola, V[G])
       while cola != 0 do
           // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición 
           // de Cola de prioridad
           u = extraer_minimo(cola) 
           for v ∈ adyacencia[u] do
               if ((v ∈ cola) && (distancia[v] > peso(u, v)) do
                   padre[v] = u
                   distancia[v] = peso(u, v)
                   actualizar(cola,v);

Código en JAVA

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;
    }
}

Demostración

Sea un grafo conexo y ponderado.

En toda iteración del algoritmo de Prim, se debe encontrar una arista que conecte un nodo del subgrafo a otro nodo fuera del subgrafo.

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

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

Sea el árbol recubridor mínimo de .

Si es el árbol recubridor mínimo.

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

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

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

Ejemplo de ejecución del algoritmo

Image Descripción No visto En el grafo En el árbol
Este es el grafo ponderado de partida. No es un árbol ya que requiere que no haya circuitos y en este grafo los hay. Los números cerca de las aristas indican el peso. Ninguna de las aristas está marcada, y el vértice D ha sido elegido arbitrariamente como el punto de partida. C, G A, B, E, F D
El segundo vértice es el más cercano a D: A está a 5 de distancia, B a 9, E a 15 y F a 6. De estos, 5 es el valor más pequeño, así que marcamos la arista DA. C, G B, E, F A, D
El próximo vértice a elegir es el más cercano a D o A. B está a 9 de distancia de D y a 7 de A, E está a 15, y F está a 6. 6 es el más chico, así que marcamos el vértice F y a la arista DF. C B, E, G A, D, F
El algoritmo continua. El vértice B, que está a una distancia de 7 de A, es el siguiente marcado. En este punto la arista DB es marcada en rojo porque sus dos extremos ya están en el árbol y por lo tanto no podrá ser utilizado. null C, E, G A, D, F, B
Aquí hay que elegir entre C, E y G. C está a 8 de distancia de B, E está a 7 de distancia de B, y G está a 11 de distancia de F. E está más cerca, entonces marcamos el vértice E y la arista EB. Otras dos aristas fueron marcadas en rojo porque ambos vértices que unen fueron agregados al árbol. null C, G A, D, F, B, E
Sólo quedan disponibles C y G. C está a 5 de distancia de E, y G a 9 de distancia de E. Se elige C, y se marca con el arco EC. El arco BC también se marca con rojo. null G A, D, F, B, E, C
G es el único vértice pendiente, y está más cerca de E que de F, así que se agrega EG al árbol. Todos los vértices están ya marcados, el árbol de expansión mínimo se muestra en verde. En este caso con un peso de 39. null null A, D, F, B, E, C, G

Referencias

Enlaces externos