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.