Utilidad del algoritmo

Cuando aplicamos el algoritmo de Kruskal a un grafo podemos obtener el árbol de coste mínimo o de coste máximo de dicho grafo.

Explicación general del algoritmo

Partimos de un grafo no dirigido (Las aristas se pueden recorrer en ambos sentidos) y ponderado (Todas las aristas tienen un coste o peso asociado).

1. Escribimos las aristas pertenecientes al grafo acompañado de su coste, se escriben en orden ascendente si queremos obtener el árbol de mínimo coste o en orden descendiente si queremos obtener el árbol de coste máximo
2. Vamos tomando cada una de las aristas en el orden establecido siempre que no cerremos un ciclo, es decir que no nos conduzca a un nodo que ya fue recorrido, en caso de que la siguiente arista cierre un ciclo entonces saltamos a la siguiente.
3. Repetimos el proceso hasta que no podamos llegar a un nuevo nodo ya que la únicas opciones posibles cierran ciclos, también nos damos cuenta que finalizamos porque la cantidad de aristas es igual a la cantidad de nodos del grafo - 1.
4. Hacemos la suma de todas las aristas recorridas y obtenemos el coste total del grafo, será mínimo o máximo según el orden que hayamos establecido al comienzo.

Ejemplo detallado de Kruskal

Partimos del siguiente grafo y vamos a conseguir tanto el árbol de mínimo coste y también el de máximo coste.

Obtención de árbol de coste mínimo:

1- Escribimos todas las aristas junto a su peso y en orden creciente

2- Tomamos la primer arista en la lista

3- Comprobamos si no cierra un ciclo y tomamos la siguiente arista en lista

4- Comprobamos si no cierra un ciclo y tomamos la siguiente arista en lista,