PrimoProgetto2002 < Architetture2/MZ

Chiusura Transitiva di un Grafo

Si calcoli la chiusura transitiva di un grafo diretto (cioe' con archi orientati) con al più 32 nodi.

Il grafo dev'essere rappresentato sotto forma di matrice di adiacenza.
La matrice di adiacenza di un grafo è una matrice a valori in {0,1} in cui esiste un 1 alle coordinate i,j se e solo se l'arco i->j è presente nel grafo.
Dato che il grafo contiene al più 32 nodi è possibile rappresentare tutta una riga della matrice di adiacenza come una stringa di 32 bits, ossia una word.
Per rappresentare tutta la matrice saranno quindi necessarie al più 32 words (una per riga).

La chiusura transitiva di un un grafo si calcola come segue:

per ogni tripla i,j,k con j,j,k tra 1 e numnodi
- se esistono l'arco i->j e l'arco j->k si inserisce (se manca) l'arco i->k
se nel passo precedente si è inserito almeno un arco si ripete il passo

Il grafo a -> b -> c -> d si trasforma in due passi come segue:

scrivere una procedura di input che permetta di inserire gli archi del grafo creando la matrice di adiacenza
- chiede il numero di nodi N (tra 1 e 32)
- chiede il numero di archi da inserire (tra 1 e N*N)
- per ogni arco chiede il primo nodo ed il secondo
scrivere una procedura di output che stampa la matrice di adiacenza del grafo:
- per ogni riga si stampi un asterisco nella colonna corrispondente a ciascun 1 presente nella riga
scrivere il programma (per controllare le procedure di I/O) che:
- chiede il grafo e costruisce la matrice di adiacenza
- stampa la matrice di adiacenza del grafo
scrivere il programma che:
- chiede il grafo e costruisce la matrice di adiacenza
- calcola la chiusura transitiva del grafo
- stampa la matrice di adiacenza del grafo