Aniello Murano » 20.Esercitazione di laboratorio: Problema del venditore Seconda parte

Esercizio

• Si consideri nuovamente il problema del venditore introdotto nella precedente lezione di laboratorio. Si implementino in modo efficiente, descrivendone le scelte opportune e le complessità asintotiche, le seguenti due operazioni:
• Il venditore vuole vendere una connessione ad internet via cavo ai suoi clienti. Implementare in linguaggio C una funzione efficiente che permetta di definire la lunghezza minima di cavo necessaria per collegare tutte le città, partendo dalla città del venditore e sfruttando soltanto i collegamenti esistenti tra le città (senza tener necessariamente conto delle loro direzioni).

Esercizio

Si supponga inoltre che una volta completato il lavoro precedente, il venditore voglia visitare tutte le città per riscuotere il pagamento del servizio dato. Si implementi dunque una funzione efficiente in linguaggio C che permetta di visitare tutte le città, rispettando i collegamenti e le direzioni esistenti tra le varie città. Tale funzione deve indicare:

• l’ordine di visita
• la distanza totale percorsa
• la somma riscossa
• le eventuali città che non sono raggiungibili

Esercizio

• Le funzioni precedenti devono gestire anche la possibilità di modifica del numero di città e di collegamenti. In pratica, se un collegamento tra due città salta, bisogna ristabilire il collegamento internet tra per tutte le città utilizzando la parte di rete rimanente.
• Si implementino in linguaggio C le operazioni precedenti utilizzando come struttura dati di appoggio un grafo, indipendentemente dal fatto che esso sia rappresentato con liste di adiacenza o con matrice di adiacenza.