Implementation (Part 2)
Lección 6 de 9 del curso Algoritmo de Kruskal - Algoritmos de grafos de Coddy.
Ahora añade la arista segura más barata hasta que el MST esté completo.
Desafío
IntermedioAhora construye el MST.
Escribe una función llamada kruskal que reciba n y el arreglo plano edges (triplas, no dirigidas) de un grafo conectado, y devuelva el peso total de su Árbol de Expansión Mínima (MST).
Toma repetidamente la arista no utilizada más barata; si sus extremos están en conjuntos diferentes, únelos y suma su peso; de lo contrario, omítela.
Reutiliza la idea de union-find de la lección anterior.
Pruébalo tú mismo
#include <stdlib.h>
int kruskal(int n, int* edges, int edges_size) {
// Escribe el código aquí
return 0;
}
Ponte a pruebaEsta lección incluye un breve cuestionario. Empieza la lección para responderlo y registrar tu progreso.
Todas las lecciones de Algoritmo de Kruskal - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity