Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 23.Esercitazione di laboratorio: Gestione di grafi indipendente dall'implementazione


Primo esercizio

Siano G e H due grafi orientati pesati di n vertici 0,1,…, n-1 rappresentati con liste di adiacenza utilizzando la struttura in figura.


Primo esercizio

Scrivere in linguaggio C una funzione che restituisca un nuovo grafo T unione dei due grafi G e H, rappresentato con liste di adiacenza, secondo la struttura dati graph definita sopra.

In pratica, T avrà tutti i vertici di G e H e conterrà un arco da un nodo i a un nodo j se tale arco è presente almeno in uno dei due grafi G e H, Per ogni arco aggiunto in T, se l’arco è presente solo in uno dei due grafi, allora l’arco erediterà il peso dell’arco presente nel grafo di partenza. Se invece l’arco è presente in entrambi i grafi G e H, allora il suo peso sarà il minore tra i due pesi associati all’arco nei due grafi di partenza.

Secondo esercizio

Si consideri un grafo G orientato non pesato di n vertici 0,1,…,n-1, rappresentato con liste di adiacenza secondo la struttura definita nel primo esercizio. Si scriva in linguaggio C una funzione che prenda in input il grafo G rappresentato con liste di adiacenza e restituisca un grafo T rappresentato con matrice di adiacenza. In pratica, la matrice T dovrà avere dimensione n x n e dovrà essere riempita utilizzando la seguente regola:

per ogni vertice i, j< n,

G[i][j]=1 se esiste un arco da i a j in G e 0 altrimenti.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion