UNIVERSIDAD PANAMERICANA

Facultad de Ciencias Aplicadas

Ingeniería en Sistemas

Matemática de computo

Algoritmo de Prim y Kruskal

José Leonardo Mateo Salazar (201800937)

Huehuetenango, Huehuetenango octubre de 2018

ALGORITMO DE PRIM

El algoritmo de Prim permite encontrar un árbol recubridor mínimode un grafo.

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
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 algoritmo podría ser informalmente descrito siguiendo los siguientes pasos:
Inicializar un árbol con un único vértice, elegido arbitrariamente del grafo.
Aumentar el árbol por un lado. Llamamos lado a la unión entre dos vértices: de las posibles
uniones que pueden conectar el árbol a los vértices que no están aún en el árbol, encontrar
el lado de menor distancia y unirlo al árbol.
Repetir el paso 2 (hasta que todos los vértices pertenezcan al árbol)
Para hacerlo más en detalle, debe ser implementado el pseudocódigo siguiente.
Asociar con cada vértice v del grafo un número C[v] (el mínimo coste de conexión a v) y a
un lado E[v] (el lado que provee esa conexión de mínimo coste). Para inicializar esos
valores, se establecen todos los valores de C[v] a +∞ (o a cualquier número más grande que
el máximo tamaño de lado) y establecemos cada E[v] a un valor "flag"(bandera) que indica
que no hay ningún lado que conecte v a vértices más cercanos.
Inicializar un bosque vacío F y establecer Q vértices que aún no han sido incluidos
en F (inicialmente, todos los vértices).
Repetir los siguientes pasos hasta que Q esté vacío:
Encontrar y eliminar un vértice v de Q teniendo el mínimo valor de C[v]
Añadir v a F y, si E[v] no tiene el valor especial de "flag", añadir también E[v] a F
Hacer un bucle sobre los lados vw conectando v a otros vértices w. Para cada lado,
si w todavía pertenece a Q y vw tiene tamaño más pequeño que C[w], realizar los
siguientes pasos:
Establecer C[w] al coste del lado vw
Establecer E[w] apuntando al lado vw
Devolver F
Como se ha descrito arriba, el vértice inicial para el algoritmo será elegido arbitrariamente,
porque la primera iteración del bucle principal del algoritmo tendrá un número de vértices
en Q que tendrán todos el mismo tamaño, y el algoritmo empezará automáticamente un
nuevo árbol en F cuando complete un árbol de expansión a partir de cada vértice conectado
del grafo. El algoritmo debe ser modificado para empezar con cualquier vértice
particular s para configurar C[s] para que sea un número más pequeño que los otros valores
de C(por norma, cero), y debe ser modificado para sólo encontrar un único árbol de
expansión y no un bosque entero de expansión, parando cuando encuentre otro vértice con
"flag" que no tiene ningún lado asociado.
Hay diferentes variaciones del algoritmo que difieren unas de otras en cómo
implementar Q: Como una única Lista enlazada o un vector de vértices, o como una
estructura de datos organizada con una cola de prioridades, más compleja. Esta elección
lidera las diferencias en complejidad de tiempo del algoritmo. En general, una cola de
prioridades será más rápida encontrando el vértice v con el mínimo coste, pero ello
conllevará actualizaciones más costosas cuando el valor de C[w] cambie.
Pseudocódigo del algoritmo[editar]
Estructura de datos auxiliar: Cola de prioridad (se puede implementar con un heap)
Prim (Grafo G)
/* 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[u]=0
mientras !esta_vacia(cola) hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el mínimo 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]>)
Algoritmo de Kruskal

El algoritmo de Kruskal calcula un árbol recubridor mínimo de un grafo.

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol
recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de
aristas que, formando un árbol, incluyen todos los vértices y donde el valor de la suma de
todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque
expandido mínimo (un árbol expandido mínimo para cada componente conexa). Este
algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956.1 2
. Otros algoritmos que sirven para hallar el árbol de expansión mínima o árbol recubridor
mínimo es el algoritmo de Prim, el algoritmo del borrador inverso y el algoritmo de
Boruvka.
Descripción
El algoritmo de Kruskal es un ejemplo de algoritmo voraz que funciona de la siguiente
manera:
se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es
un árbol separado
se crea un conjunto C que contenga a todas las aristas del grafo
mientras C es no vacío
eliminar una arista de peso mínimo de C
si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles
en un solo árbol
en caso contrario, se desecha la arista
Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de
expansión mínimo del grafo.
En un árbol de expansión mínimo se cumple:
la cantidad de aristas del árbol es la cantidad de nodos menos uno (1).
Pseudocódigo
función Kruskal(G)
Para cada v en V[G] hacer
Nuevo conjunto C(v) ← {v}.
Nuevo heap Q que contiene todas las aristas de G, ordenando por su peso.
Defino un arbol T ← Ø
// n es el número total de vértices
Mientras T tenga menos de n-1 aristas y ![Link]ío() hacer
(u,v) ← [Link]()
// previene ciclos en T. agrega (u,v) si u y v están diferentes componentes en el conjunto.
// Nótese que C(u) devuelve la componente a la que pertenece u.
Si C(v) ≠ C(u) hacer
Agregar arista (v,u) a T.
Merge C(v) y C(u) en el conjunto
Responder arbol T