Algoritmo de Kruscal Java

Kruskal propone otra estrategia para encontrar el árbol de expansión de coste mínimo. El árbol
se empieza a construir con todos los vértices del grafo G pero sin aristas; se puede afirmar
que cada vértice es una componente conexa en sí misma. El algoritmo construye componentes
conexas cada vez mayores examinando las aristas del grafo en orden creciente del peso. Si la
arista conecta dos vértices que se encuentran en dos componentes conexas distintas, entonces se
añade la arista al árbol de expansión T. En el proceso, se descartan las aristas que conectan dos
vértices pertenecientes a la misma componente, ya que darían lugar a un ciclo si se añaden al
árbol de expansión ya que están en la misma componente. Cuando todos los vértices están en un
solo componente, T, éste es el árbol de expansión de coste mínimo del grafo G.
El algoritmo de Kruskal asegura que el árbol no tiene ciclos, ya que para añadir una arista, sus
vértices deben estar en dos componentes distintas; además es de coste mínimo, ya que examina
las aristas en orden creciente de sus pesos.
La Figura 16.7 muestra un grafo y, a continuación, se obtiene su árbol de expansión, aplicando
este algoritmo. En primer lugar se obtiene la lista de aristas en orden creciente de sus pesos:
{(1,3), (1,2), (2,4), (1,5), (2,3), (3,4), (5,6), (4,5), (1,6)}
La primera arista que se toma es (1,3), como muestra la Figura 16.10a; a continuación, las
aristas (1,2), (2,4) y (1,5), en las que se cumple que los vértices forman parte de dos componentes
conexas diferentes, como se observa en la Figura 16.10b. La siguiente arista, (2,3) como sus
vértices están en la misma componente, por tanto se descarta; la arista (3,4) por el mismo motivo
se descarta. Por último, la arista (5,6), que tiene sus vértices en dos componentes diferentes, pasa
a formar parte del árbol, y el algoritmo termina ya que se han alcanzado todos los vértices.