4.3.2. Árboles de expansión.
Dado un grafo ponderado G=(V, A), el algoritmo parte de un grafo G’= (V, Ø). Cada nodo es una componente conexa en sí misma.
En cada paso de ejecución se elige la arista de menor costo de A.
- Si une dos nodos que pertenecen a distintas componentes conexas entonces se añade al árbol de expansión G’.
- En otro caso no se coge, ya que formaría un ciclo en G’.
Acabar cuando G’ sea conexo: cuando tengamos n-1 aristas.
Estructura del algoritmo de Kruskal
Sea T de tipo Conjunto de aristas, el lugar donde se guardarán las aristas del árbol de expansión. Asignar T a Ø.
Mientras T contenga menos de n-1 aristas hacer:
- Elegir la arista (v, w) de A con menor costo.
- Borrar (v, w) de A (para no volver a cogerla).
- Si v, w están en distintos componentes conexos entonces añadir (v, w) a T. En otro caso, descartar (v, w).