Dos algoritmos voraces

Sobre Prim Y Kruskal

(Para los chicos de UPN)

Evolución del Algoritmo de Kruskal

Siguiendo el desarrollo de la teoría de grafos es importante mencionar  un tema fundamental como lo es árboles. Se entiende por árbol (en esta parte de las matemáticas) a un grafo (no digrafo) conexo y  acíclico. Ahora bien, dentro de  estos conceptos encontramos a arboles generadores mínimos.

Para encontrar árboles generadores mínimos debemos mencionar a Prim y Kruskal, dos personajes que han contribuido con métodos de identificación (algoritmos) facilitando el reconocimiento de árboles generadores mínimos.

Los algoritmos tanto de Prim como de Kruskal (con bastante parecido) permiten la construcción de árboles generadores mínimos. Ambos actúan añadiendo aristas de peso mínimo de manera secuencial  al recorrido de tal manera que estos algoritmos (algoritmos voraces) permiten obtener soluciones óptimas de un problema dado. Si bien es cierto que ambos  son muy parecidos, en cuanto a la metodología, debemos establecer una diferencia bien pronunciada en cuanto a estos se refiere.

 En el algoritmo de Prim las aristas de peso mínimo deben ser incidentes con alguno de los vértices del árbol ya construido y no deben formar un ciclo con las ya añadidas; mientras que en el algoritmo de Kruskal las aristas de peso mínimo si bien es cierto no pueden formar un ciclo con las ya elegidas, pero no deben ser necesariamente incidentes con vértices del árbol. Estas serían fundamentalmente la diferencia más notable entre estos dos algoritmos. Cabe indicar también que al inicio en el algoritmo de Prim la arista asignada es la de peso mínimo; mientras que en el algoritmo de Kruskal se le asigna un grafo vacío.