LabASD - Algoritmo di Kruskal

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-05-20

In questo esercizio si chiede di implementare l'algoritmo di Kruskal per il calcolo di un Minimum Spanning Tree (MST) di un grafo non orientato pesato \(G=(V, E, w)\). L'algoritmo opera secondo i passi seguenti:

Per implementare efficientemente l'algoritmo di Kruskal serve un modo rapido per verificare se due nodi appartengono o no allo stesso albero della foresta. A tale scopo possiamo usare una struttura merge-find oggetto di un'altra esercitazione.

Per ordinare gli archi si può implementare un algoritmo di ordinamento, oppure usare la funzione qsort() dichiarata nell'header file <stdlib.h>. L'interfaccia della funzione è la seguente:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

dove:

Il programma deve leggere il grafo da standard input, e deve stampare l'elenco degli archi che fanno parte del MST su standard output. Il formato dell'input è quello della struttura Graph.

Il programma stampa l'elenco degli archi che fanno parte del MST, nello stesso formato dell'input. Sarebbe quindi possibile usare l'output di una esecuzione di questo programma come input al programma stesso.

Come si vede, questo programma non fa uso della struttura dati Graph che abbiamo visto in un precedente laboratorio. Infatti, per come funziona l'algoritmo di Kruskal, è sufficiente che il grafo sia rappresentato mediante un elenco di archi. Nel nostro caso usiamo un array E[] di strutture di tipo Edge per semplificarne l'ordinamento. Il MST viene memorizzato in un array di puntatori mst[] (Figura 1), che deve essere inizializzato ad una lunghezza opportuna; si suggerisce di usare come lunghezza di default il massimo numero di archi che possano far parte di un MST (si vedano le domande). La variabile globale nmst indica il numero effettivo di archi che fanno parte del MST.

Figura 1: Grafo orientato e rappresentazione di un suo MST
Figura 1: Grafo orientato e rappresentazione di un suo MST

Per compilare da riga di comando:

    gcc -std=c90 -Wall -Wpedantic kruskal.c mfset.c -o kruskal

Per eseguire:

    ./kruskal < graph10.in

oppure

    ./kruskal graph10.in

Domande

File