Algoritmo de Kruskal

Este algoritmo toma su nombre de Joseph Kruskal, quien lo publicó por primera vez en 1956.

Incluso una estructura de datos sobre conjuntos disjuntos simple con uniones por rangos puede ejecutar las operaciones mencionadas en O(m log n).

Sea T=[X,A] la gráfica generada por el algoritmo de Kruskal.

Para ello se procederá de la siguiente manera: A partir de los árboles T y S se construirá otro árbol, S1=[X,A´´], de costo mínimo de G con la característica que es más "parecido" a T que S; esto es, si T y S tienen k aristas en común, T y S1 tendrán k+1 aristas en común.

Por otro lado, como Sr-1 es árbol, existe en él una cadena que une los extremos de u1.

Esta cadena contiene una arista u2, que no pertenece a T, puesto que si estuviera toda la cadena se formaría un ciclo con u1 en T. Agréguese u1 a Sr-1 y elíminese u2 de Sr-1.

Esto es una contradicción, puesto que b1, b2 ,...,bi y u2 formarían ciclo en Sr-1 .