algoritmos

 Instituto Politécnico Nacional

Escuela Superior de Cómputo






Alumno:Asignatura:

Análisis de Algoritmos






Profesor:

Edgardo Adrian Franco Martínez






ALGORITMOS ÁVIDOSGrupo:

3CM4




Algoritmo de Kruskal
Josep b. Kruskal investigador del Math Center, que en 1956 descubriósu algoritmo para la resolución del problema del Árbol de coste total mínimo (mínimum spanning tree-MST) también llamado árbol recubridor euclideo mínimo.
Objetivo.
El objetivo del algoritmo deKruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Explicacion:
El algoritmo de Kruskal queresuelve la misma clase de problema que el de Prim, salvo que en esta ocasión no partimos desde ningún nodo elegido al azar. Para resolver el mismo problema lo que hacemos es pasarle a la función unalista con las aristas ordenadas de menor o mayor e iremos tomando una para formar el ARM.
Algoritmo de Kruskal.
El algoritmo de Kruskal permite hallar el árbol mínimo de cualquier grafo valorado (concapacidades). Hay que seguir los siguientes pasos:
Pasó 1: Se marca la arista con menor valor. Si hay más de una, se elige cualquiera de ellas.
Pasó 2: De las aristas restantes, si hay más de una, seelige cualquiera de ellas.
Nota: Repetir el paso 2 siempre que la arista elegida no forme un ciclo con las ya marcadas.
Pasó 3: El rpoceso termina cuando tenemos todos los nodos del grafo el algunade las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos siendo n el numero de nodos por grafo.
Capturas de Pantalla:


















Algoritmo de Prim
Robert Prim...