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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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