Implementazione (Parte 2)
Lezione 6 di 9 del corso Algoritmo di Kruskal - Algoritmi sui grafi di Coddy.
Ora aggiungi l'arco sicuro più economico finché l'albero ricoprente minimo non è completo.
Sfida
MedioOra costruisci l'MST.
Scrivi una funzione chiamata kruskal che accetta n e l'array piatto edges (terne, non orientato) di un grafo connesso e restituisce il peso totale del suo albero ricoprente minimo.
Prendi ripetutamente l'arco inutilizzato più economico; se i suoi estremi appartengono a insiemi diversi, uniscili e aggiungi il suo peso; altrimenti, saltalo.
Riutilizza l'idea di union-find della lezione precedente.
Provalo tu
#include <stdlib.h>
int kruskal(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 Kruskal - Algoritmi sui grafi
2L'algoritmo
Come funziona?PseudocodiceImplementazione (Parte 1)Implementazione (Parte 2)
Complessità temporale e spazialeEsercitati da solo: Compilatore C online