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

---+++ Esempio

Il grafo ==a -> b -> c -> d== si trasforma in due passi come segue:
<table border=1 align=center><tr align=center><td>
<IMG SRC="/cgi-bin/webdot%ATTACHURLPATH%/grafo1.dot.dot.png"/>
| -> | a | b | c | d |
|  a | 0 | 1 | 0 | 0 |
|  b | 0 | 0 | 1 | 0 |
|  c | 0 | 0 | 0 | 1 |
|  d | 0 | 0 | 0 | 0 |
</td><td>
<IMG SRC="/cgi-bin/webdot%ATTACHURLPATH%/grafo2.dot.dot.png"/>
| -> | a | b | c | d |
|  a | 0 | 1 | <font color=red>1</font> | 0 |
|  b | 0 | 0 | 1 | <font color=red>1</font> |
|  c | 0 | 0 | 0 | 1 |
|  d | 0 | 0 | 0 | 0 |
</td><td>
<IMG SRC="/cgi-bin/webdot%ATTACHURLPATH%/grafo3.dot.dot.png"/>
| -> | a | b | c | d |
|  a | 0 | 1 | 1 | <font color=red>1</font> |
|  b | 0 | 0 | 1 | 1 |
|  c | 0 | 0 | 0 | 1 |
|  d | 0 | 0 | 0 | 0 |
</td></tr><table>

---+++ Svolgimento:
   * 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


Se avete domande sul testo del progetto, fatele su DomandePrimoProgetto2002

-- Users.AndreaSterbini - 26 Mar 2002
<!--
   * Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
-->
This topic: Architetture2/MZ > DateEScadenze > PrimoProgetto2002
Topic revision: r4 - 2002-03-30 - AndreaSterbini