Algoritmo de Kruskal

1. Comience seleccionando la arista de menor longitud.
2. En cada interacción agregue la siguiente arista de menor longitud del conjunto de aristas disponibles, teniendo la precaución de no formar ningún ciclo.
3. El algoritmo terminara cuando todos las aristas estén conectados. Si N = numero de nodos la solución optima debe incluir N-1 aristas.

Ejemplo:
Este es el grafo original. Los números de las aristas indican su peso. Ninguna de las aristas está resaltada.

AD y CE son las aristas más cortas, con peso 5, y AD se ha elegido arbitrariamente por tanto se resalta.

Sin embargo, ahora es CE la arista más pequeña que no forma ciclos, con peso 5, por lo que se resalta como segunda arista.

La siguiente arista, DF con peso 6, ha sido resaltada utilizando el mismo método.

La siguientes aristas más pequeñas son AB y BE, ambas con peso 7. AB se elige arbitrariamente, y se resalta. La arista BD se resalta en rojo, porque formaría un ciclo ABD si se hubiera elegido.

El proceso continúa marcando las aristas, BE con peso 7. Muchas otras aristas se marcan en rojo en este paso: BC (formaría el ciclo BCE),DE (formaría el ciclo DEBA), y FE (formaría el ciclo FEBAD).

Finalmente, el proceso termina con la arista EG de peso 9, y se ha encontrado el árbol de expansión mínima con peso total de 39.