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

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.