algoritmo de kruskall

Algoritmo de Kruskal
El siguiente es el algoritmo propuesto por Kruskal el año de 1956 para encontrar el árbol de expansión mínimo en un grafo valorado y nodirigido. El algoritmo de Kruskal busca un subconjunto de aristas que incluyan todos los vértices y donde el valor total de todas las aristas sea la mínima.
Esta versiónestá pensada para implementarse en lista de Adyacencia. Recibe un grafo G a partir del cual encuentra un árbol de expansión (que es otro grafo) y el costo total mínimo. Enun grafo con N Vértices y A Aristas, el algoritmo es del orden O(A log A) para ordenar las aristas por distancia, O(log A) para sacar una arista N veces, con un pocode matemática se llega a que el tiempo total es O( A log N) si el grafo está conectado.

Antes de llamar al algoritmo se debe inicializar Padre con el mismo valorde su vértice, el resto de los atributos no se usan.
Kruskal (G) -> AE, total
ColaPrioridad ColaP // Se puede usar montículo MIN ordenado por DistanciaG.Llenar (ColaP) // Este montículo tiene 3 atributos: Distancia, Vértice Origen y Vértice Destino
Se lo llena con todas las aristas del grafocont=0;
Mientras ( cont < A ) // A es la cantidad de todas las aristas del grafo, podría ser salida de llenar
Trio = ColaP.Sacar() // TRIO es el de menor DistVo = BuscarCiclo (Trio.Vo)
Vd = BuscarCiclo (Trio.Vd)
Si (Vo Vd)
AE.InsertarArista(Vo,Vd, Trio.Distancia)
Total=total+Trio.Distancia
G[Vo].padre=G[Vd].padre
cont=cont+1

Terminar Devolviendo AE y Total
BuscarCiclo (x) -> x
Mientras ( x G[x].padre)
x = G[x].padre
Terminar Devolviendo x