Implementation (Part 2)
Lección 6 de 9 del curso Algoritmo de Prim - Algoritmos de grafos de Coddy.
Ahora haz crecer el árbol, añadiendo siempre la arista de cruce más barata.
Desafío
IntermedioAhora haz crecer el árbol completo.
Escribe una función llamada prim que reciba n y el array plano edges (triplas, no dirigido) de un grafo conexo, y devuelva el peso total del Árbol de Recubrimiento Mínimo, comenzando el árbol desde el vértice 0.
Mantén una bandera inTree por cada vértice. En cada ronda, encuentra la arista más barata con exactamente un extremo en el árbol, añade su peso e incorpora su extremo exterior al árbol.
Pruébalo tú mismo
#include <stdlib.h>
int prim(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 Prim - Algoritmos de grafos
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity