Esquema del algoritmo de Kruskal: G= (V, A)
- Empezar con un grafo sin aristas: G’= (V, Ø)
- Seleccionar la arista de menor coste de A.
- Si la arista seleccionada forma un ciclo en G’, eliminarla. Si no, añadirla a G’.
- Repetir los dos pasos anteriores hasta tener n-1 aristas.
• ¿Cómo saber si una arista (v, w) provocará un ciclo en el grafo G’?
Implementación del algoritmo
• Necesitamos:
– Ordenar las aristas de A, de menor a mayor: O(a log a).
– Saber si una arista dada (v, w) provocará un ciclo.
• ¿Cómo comprobar rápidamente si (v, w) forma un ciclo?
• Una arista (v, w) forma un ciclo si v y w están en el mismo componente conexo.
• La relación “estar en el mismo componente conexo” es una relación de equivalencia.
• Usamos la estructura de relaciones de equivalencia con punteros al padre:
– Inicialización: crear una relación de equivalencia vacía (cada nodo es un componente conexo).
– Seleccionar las aristas (v, w) de menor a mayor.
– La arista forma ciclo si: Encuentra(v) = Encuentra(w)
– Añadir una arista (v, w): Unión(v, w) (juntar dos componentes conexos en uno).
• Analizar y responder la siguiente pregunta.
¿Cuál es el orden de complejidad del algoritmo?
Conclusiones
• Ambos algoritmos (Prim y Kruskal) encuentran siempre la solución óptima.
• ¿ La solución obtenida será la misma, o no...?
• La estructura de los dos algoritmos es muy parecida:
– Empezar con una solución “vacía”.
– Añadir en cada paso un elemento a la solución (Prim: un nodo; Kruskal: una arista).
– Una vez añadido un elemento a la solución, no se quita (no se “deshacen” las decisiones tomadas).
Consultar el siguiente Link:
https://elibro.bibliotecabuap.elogim.com/es/ereader/bibliotecasbuap/50117?page=506