arbol de expancion

Árbol de Expansión
Dado un grafo conexo, no dirigido G. Un árbol de expansión es un árbol compuesto por todos los vértices y algunas (posiblemente todas) de las aristas de G. Al ser creado un árbolno existirán ciclos, además debe existir una ruta entre cada par de vértices.
Un grafo puede tener muchos arboles de expansión, veamos un ejemplo con el siguiente grafo:

En la imagen anterior sepuede observar que el grafo dado posee 3 arboles de expansión, dichos arboles cumplen con las propiedades antes mencionadas como son unir todos los vértices usando algunas aristas.
Árbol de ExpansiónMínima
Dado un grafo conexo, no dirigido y con pesos en las aristas, un árbol de expansión mínima es un árbol compuesto por todos los vértices y cuya suma de sus aristas es la de menor peso. Alejemplo anterior le agregamos pesos a sus aristas y obtenemos los arboles de expansiones siguientes:

De la imagen anterior el árbol de expansión mínima seria el primer árbol de expansión cuyo pesototal es 6.
El problema de hallar el Árbol de Expansión Mínima (MST) puede ser resuelto con varios algoritmos, los mas conocidos con Prim y Kruskal ambos usan técnicas voraces (greedy).
Algoritmo deKruskal
Para poder comprender el algoritmo de kruskal será necesario revisar primer el tutorial de Union-Find.
Como trabaja:
Primeramente ordenaremos las aristas del grafo por su peso de menor amayor. Mediante la técnica greedy Kruskal intentara unir cada arista siempre y cuando no se forme un ciclo, ello se realizará mediante Union-Find. Como hemos ordenado las aristas por peso comenzaremos conla arista de menor peso, si los vértices que contienen dicha arista no están en la misma componente conexa entonces los unimos para formar una sola componente mediante Union(x , y), para revisar siestán o no en la misma componente conexa usamos la función SameComponent(x , y) al hacer esto estamos evitando que se creen ciclos y que la arista que une dos vértices siempre sea la mínima posible....