LabASD - Algoritmo di Prim

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-05-07

Implementare l'algoritmo di Prim per il calcolo del Minimum Spanning Tree (MST) di un grafo non orientato pesato. L'algoritmo di Prim richiede un nodo di partenza \(s\), e opera sfruttando una coda di priorità (che abbiamo già implementato nei file minheap.c e minheap.h).

Per inizializzare le distanze a \(+\infty\) si può usare il valore HUGE_VAL definito in <math.h> che rappresenta l'infinito positivo. Questo simbolo è definito nello standard C90, per cui dovrebbe essere presente in tutti i compilatori compatibili.

Il programma legge il grafo da standard input, e stampa l'elenco degli archi che fanno parte del MST su standard output. 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:

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

Per compilare:

    gcc -std=c90 -Wall -Wpedantic graph.c minheap.c prim.c -o prim

Per eseguire:

    ./prim < graph10.in

oppure

    ./prim graph10.in

Domande

File