# Programación en Java/Apéndices/Implementación del Algoritmo de Kruskal en Java

El algoritmo de Kruskal es un algoritmo de la teoría de grafos que busca encontrar un árbol recubridor mínimo de un grafo dado. Aquí encontraremos una implementación en Java incluyendo una interfaz gráfica.

## Descripción del Problema

El algoritmo de kruskal, es un algoritmo voraz utilizado en la teoría de grafos, con el fin de encontrar un árbol recubridor mínimo de un grafo conexo y ponderado.
El algoritmo de kruskal consiste en:
* Paso 0: Iniciar el árbol T con n nodos y sin arcos
* Paso 1: Con los arcos de G crear una lista L de arcos, en orden ascendente de peso. Los arcos con el mismo peso son ordenados arbitrariamente.
* Paso 2. Seleccionar el arco (i,j) que esté al comienzo de L. Si éste forma un circuito en T no se transfiere a T y se borra de L y se repite el paso 2. Si no forma circuito en T se transfiere a T y se borra de L.
* Paso 3. Si L es no vacío, volver al paso 2, de lo contrario PARAR.

## Limitaciones

Las únicas limitaciones que se presentan con el problema de la implementación del algoritmo de Kruskal es la creación de un algoritmo adicional que nos compruebe que al adicionar una arista al grafo no nos haga un ciclo.
El algoritmo implementado es el siguiente:

## Solución

En la implementación del algoritmo de Kruskal en Java, se hizo uso de una estructura de datos adicional llamada grafo y adicionalmente se implementó una interfaz gráfica.

### Estructura Grafo
#### Clase Enlace

// creamos un clase llamada enlace
La clase enlace se utiliza para hacer refencia al nodo terminal y al peso de un arco.

#### Clase Nodo

Hace referencia a un nodo del grafo, guardando un nombre y una serie de enlaces a otros nodos.

#### Clase Arco

Guarda la referencia del nodo inicial, nodo terminal y peso de un determinado arco del grafo.

#### Clase Grafo

Representa la estructura grafo, compuesta por nodos y arcos.

### Interfaz Gráfica
#### Clase Lienzo

Es el lienzo sobre el cual se dibujará el grafo.

#### Clase Punto

Permite dibujar un punto sobre el lienzo. Hace referencia a la posición del punto sobre el lienzo.

#### Clase Arista

Permite dibujar una arista entre dos puntos sobre el lienzo. Hace referencia a los puntos.

### VENTANA
#### Clase Aplicación
## Modo de compilación y ejecución

Para poder compilar y ejecutar el programa debe tener instalado en su computador el jdk de java 1.5 o mejores actualizaciones y además debe tener el path de Windows configurado con el jdk. Más sobre configuración del path
Antes de comenzar tiene que copiar cada una de las clases en un bloc de notas separado y guardarlo con el mismo nombre de la clase y con extensión .java. Por ejemplo: al copiar la clase AlgoritmoKruskal en un bloc de notas la guarda como AlgoritmoKruskal.java.
Para compilar abra la consola, o para Windows XP la herramienta símbolo del sistema, estando allí diríjase al directorio donde tiene todas las clases guardadas (Todas las clases deben estar en el mismo directorio para que el programa corra correctamente) y enseguida copie el siguiente comando javac Aplicacion.java, esto le dice a java que compile el main del programa que se encuentra en Aplicacion.java. Si hace esto correctamente deben haberse creado en el directorio de las clases varios archivos .class, uno para cada clase y con el mismo nombre de la clase.
Para ejecutar tiene que haber compilado primero. Nuevamente abra la consola, o símbolo del sistema, y diríjase al directorio donde se encuentran todas las clases y digite el siguiente comando java Aplicacion, esto le dice a java que ejecute el main del programa. Si lo hace correctamente el programa debe estar corriendo.

## Tiempo empleado

Para una implementación óptima del algoritmo haciendo uso de una interfaz grafica y una estructura adicional se hicieron necesarias alrededor de 15 horas, incluyendo el tiempo que se necesitó para investigar y complementar los conceptos necesarios para lograr el resultado obtenido y deseado.

## Tiempo de Ejecución T(n)

Sea T(n) el número de nodos que posee el grafo. Dado que se trata de un grafo denso podemos afirmar que la longitud del camino máximo será n. Igualmente cada llamada recursiva supondrá una disminución del problema en exactamente la unidad. De forma similar, puede afirmarse que el número de llamadas recursivas irá disminuyendo en uno puesto que en cada nivel hay un nodo adyacente más que ya ha sido visitado. Por último puede observarse que dentro del ciclo se realizan al menos n comparaciones. Con los hechos nombrados con anterioridad es posible establecer la siguiente relación de recurrencia: T(n) = (n-1) T(n-1) + n Siendo esta recurrencia no homogénea, es decir, en este caso la combinación lineal no es igual a cero, tal como puede verse en la siguiente expresión: A$_0$t$_n$ +a$_1$t$_{n-1}$ +…..+ a$_k$t$_{n-k}$ = b$_n$p(n)
Se procede ahora a definir el valor de b=2 y p(n)=n Obteniendo que el polinomio característico es:
(x-(n-1)) (x-1)² con raíces (n-1) (de multiplicidad 1) y 1 (de multiplicidad 2).
Por lo tanto todas las soluciones son de la forma t$_n$= c$_1$(n-1)$^n$ +c$_2$1$^n$+c$_3$n1$^n$
Siempre y cuando t0 >=0 para todo n, se concluye inmediatamente que t pertenece a O (n-1)$^n$

## Conclusiones

* El algoritmo de kruskal es sencillo de implementar con las herramientas adecuadas.
* El algoritmo de kruskal, al momento de implementarlo en algún lenguaje de programación, no es tan óptimo con respecto a otros algoritmos que cumplen el mismo objetivo, como el de Prim, debido que al momento de implementarlo se tiene la limitante de diseñar un algoritmo adicional que encuentre ciclos que en este caso no es el más óptimo.
* Al momento de implementar el algoritmo es más óptimo ordenar a medida que el usuario ingresa aristas que ordenar después de terminado el grafo. También sería bueno añadir las aristas en una cola de prioridad, ya que se evita igualmente la búsqueda de la arista menor.

## Véase también

* Algoritmo de Prim
* Algoritmo de Kruskal
* Teoría de grafos
* Algoritmo voraz

## Enlaces externos

* Animación del algoritmo de Kruskal
* Creación y solución de laberintos por los algoritmos de Kruskal y Prim
* Otra Animación (incluye código en JAVA)