Agoritmo de Kruskal

Algoritmo de Expansión mínima

 Joseph Kruskal

• Se dedico al cuasi-ordenamiento y escalamiento multidimensional

• Su mayor aporte a la informática fue el desarrollo de sus algoritmo

• Es un algoritmo voraz

• Se usa para encontrar el árbol de expansión mínima en un grafo conexo y ponderado

Árbol de expansión 

Es un Árbol compuesto por todos lo vértices y algunas de las aristas en el cual no existirán ciclos

Árbol de expansión mínima

Es un Árbol compuesto por todos lo vértices y algunas de las aristas en el cual no existirán ciclos en donde la suma de sus aristas es la de menor peso

Desarrollo

Consiste en buscar el Árbol de expansión mínima, buscando el arco de menor peso y se une a los vértices siempre y cuando no se forme un ciclo haciendo que hasta que todos los vértices estén comprendidos en el ARBOL

Para comprobar que el árbol este hecho es que el numero de aristas debe ser igual al numero de V-1, donde V es el nùmero de aristas

                                               

Pseudocodigo

 function 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 árbol T ← Ø     
   // n es el número total de vértices
   Mientras T tenga menos de n-1 vertices hacer
     (u,v) ← Q.sacarMin()
     // 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.
     if C(v) ≠ C(u) then
       Agregar arista (v,u) a  T.
       Merge C(v) y C(u) en el conjunto
   Return arbol T