ALGORITMO DE KRUSKAL


Pseudo código del algoritmo:

La idea básica consiste en elegir sucesivamente las aristas de mínimo peso sin formar ciclos.
    Paso 1. Se elige la arista de mínimo peso e y se considera S={e}.
    Paso 2. Sea e’ la arista de mínimo peso tal que e’ÏS y S+e' es un grafo acíclico. Se hace S=S+e'.
    Paso 3. Si S tiene n-1 aristas, el algoritmo termina. En caso contrario se vuelve al paso 2.

Demostración de la validez del algoritmo

En primer lugar se observa que el algoritmo construye un árbol generador. Sea T el árbol construido por el algoritmo de Kruskal y supongamos que no es de peso mínimo. Sea S un árbol generador mínimo que contenga el mayor segmento inicial de la lista de aristas elegidas para T. Llamamos e a la primera arista elegida para T que no está en S. Añadiendo la arista e a S se crea un ciclo C. Este ciclo debe contener una arista e* que no es de T, pues T no contiene ningún ciclo. Consideramos el grafo S* = S + e - e*. Este grafo es un árbol generador. Además cuando el algoritmo elige la arista e, tanto e como e* están disponibles luego w(e) £ w(e*). Por tanto S* es un árbol generador con w(S*) £ w(S), es decir, es un árbol generador mínimo y contiene una arista más de T que el árbol S (la arista e), en contradicción con la elección de S.

Análisis de la complejidad

El coste del primer paso, ordenación de las aristas según su peso, es O(qlogq), es decir, O(qlogn). En el segundo paso se debe detectar si la arista elegida forma un ciclo con las previamente elegidas. ¿Cómo? Basta tener marcada la componente conexa a que pertenece cada vértice (inicialmente habrá n componentes, una por vértice). Si se elige una arista con extremos de la misma etiqueta se está formando un ciclo y si tienen distinta etiqueta no hay ciclo y la elección es correcta. En este caso se deben actualizar las etiquetas para mantener siempre una por cada componente conexa. El coste total de este paso es O(q) por la comprobación de la corrección más O(n2) por las actualizaciones, pues en el peor caso en cada uno de los n pasos se deben actualizar las etiquetas de los n vértices. La complejidad total del algoritmo de Kruskal es por tanto O(n2+qlogn)


Applet Java.

El algoritmo se ejecuta paso a paso haciendo click en la región del applet.
El grafo sobre el que trabaja el algoritmo esta generado aleatoriamente.
Una vez acabada la ejecución del algoritmo, se puede volver a ejecutar desde el principio, ya que el estado de todos los vértices y aristas se inicializa de nuevo.





PARA OBTENER UN NUEVO GRAFO REGARGUE LA PAGINA.

Volver a la pagina principal