Algoritmo de kruscal

ALGORITMO DE KRUSKAL

Introducción
Joseph B. Kruskal investigador del Math Center (Bell-Labs), que en 1956 descubrió su algoritmo para la resolución del problema del Árbol de costo total mínimo(minimum spanning tree - MST) también llamado árbol recubridor euclídeo mínimo. El Algoritmo de Kruskal que resuelve la misma clase de problema que el de Prim, salvo que en esta ocasión no partimosdesde ningún nodo elegido al azar. Para resolver el mismo problema lo que hacemos es pasarle a la función una lista con las aristas ordenada de menor a mayor, e iremos tomando una para formar el ARM. Elobjetivo del algoritmo de Kruskal 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.

DescripciónEl algoritmo de Kruskal permite hallar el árbol mínimo de cualquier grafo valorado (con capacidades). Hay que seguir los siguientes pasos: Se marca la arista con menor valor. Si hay más de una, seelige cualquiera de ellas. De las aristas restantes, se marca la que tenga menor valor, si hay más de una, se elige cualquiera de ellas. Repetir el paso 2 siempre que la arista elegida no forme un ciclocon las ya marcadas. El proceso termina cuando tenemos todos los nodos del grafo en alguna de las aristas marcadas, es decir, cuando tenemos marcados n-1 arcos, siendo n el número de nodos del grafoAlgoritmo de kruscal

Void Kruscal(Grafo G, conjunto T) { Conjunto_V U; Vértice V; T = 0; For (cada vértice V de G) Construye un árbol con V; Ordena los arcos de G en orden no decreciente; While(Haya más de un árbol) { Sea (U, V) es el arco de menor costo tal que el árbol de u es diferente del árbol V; Mezcal los arboles de U y de V en uno solo; T = T U {(U, V)}; } }

Ejemplo de uso delalgoritmo

Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.

Se buscan las aristas con menor costo por ejemplo AD y CE son las aristas...