Implementazione (Parte 2)
Lezione 6 di 9 del corso Algoritmo di Prim - Algoritmi sui grafi di Coddy.
Ora fai crescere l'albero, aggiungendo sempre l'arco di attraversamento meno costoso.
Sfida
MedioOra fai crescere l'intero albero.
Scrivi una funzione chiamata prim che accetta n e l'array piatto edges (terne, non orientato) di un grafo connesso e restituisce il peso totale dell'albero ricoprente minimo, iniziando l'albero dal vertice 0.
Mantieni un flag inTree per ogni vertice. A ogni iterazione, trova l'arco più economico con esattamente un estremo nell'albero, aggiungi il suo peso e inserisci nell'albero il suo estremo esterno.
Provalo tu
#include <stdlib.h>
int prim(int n, int* edges, int edges_size) {
// Scrivi il codice qui
return 0;
}
Mettiti alla provaQuesta lezione include un breve quiz. Inizia la lezione per rispondere e tenere traccia dei tuoi progressi.
Tutte le lezioni di Algoritmo di Prim - Algoritmi sui grafi
2L'algoritmo
Come funziona?PseudocodiceImplementazione (Parte 1)Implementazione (Parte 2)
Complessità temporale e spazialeEsercitati da solo: Compilatore C online