Ultimo aggiornamento: 2024-01-29
Implementare l’algoritmo di Prim per il calcolo del Minimum Spanning Tree (MST) di un grafo non orientato pesato. L’algoritmo di Prim è stato scoperto dal matematico ceco Vojtěch Jarník nel 1930, e successivamente riscoperto da Robert C. Prim nel 1957; per questo è anche detto algoritmo di Jarník-Prim.
L’algoritmo richiede un nodo di partenza \(s\), che può essere scelto arbitrariamente se il grafo è connesso, e sfrutta una coda di priorità che abbiamo già implementato nei file minheap.c e minheap.h. Questo programma usa \(s=0\) come nodo di partenza.
Per inizializzare le distanze a \(+\infty\) si usi il simbolo HUGE_VAL definito in <math.h> che rappresenta l’infinito positivo1.
Il programma legge il grafo da un file il cui nome viene passato sulla riga di comando, e stampa a video l’elenco degli archi che fanno parte del MST. Il formato dell’input è lo stesso utilizzato dal tipo di dato grafo:
n m 0
s[0] d[0] w[0]
s[1] d[1] w[1]
...
s[m-1] d[m-1] w[m-1]dove:
n è il numero di nodi del grafo; i nodi sono rappresentati dagli interi \(0, \ldots, (n-1)\);
m è il numero di archi del grafo
0 indica che il grafo è non orientato
s, d, w sono rispettivamente il nodo sorgente, il nodo destinazione, e il peso di ciascun arco. I pesi sono valori reali.
Il programma stampa l’elenco degli archi che fanno parte del MST, nello stesso formato dell’input. È quindi possibile usare l’output come input al programma stesso.
Per compilare:
gcc -std=c90 -Wall -Wpedantic graph.c minheap.c prim.c -o primPer eseguire:
./prim graph10.inDato un grafo non orientato pesato e connesso con \(n\) nodi e \(m\) archi, qual è il numero massimo di archi che può far parte di un MST?
Cosa succede se applichiamo l’algoritmo di Prim ad un grafo non connesso?
In realtà la documentazione afferma che
The macros
HUGE_VAL,HUGE_VALF,HUGE_VALLexpand to constants of typesdouble,floatandlong double, respectively, that represent a large positive value, possibly positive infinity.
Il simbolo INFINITY rappresenta il valore “infinito” su processori che supportano lo standard IEEE754, ma purtroppo è definito solo da C99 in poi. INFINITY non è semplicemente “un valore grande”: ad esempio, lo standard IEEE754 impone che se \(x\) è un qualunque valore positivo finito, allora INFINITY + x == INFINITY, mentre HUGE_VAL + x potrebbe causare overflow. I compilatori che ho a disposizione sembrano definire HUGE_VAL come INFINITY, ma non è garantito che sia sempre così.↩