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:
| -> |
a |
b |
c |
d |
| a |
0 |
1 |
0 |
0 |
| b |
0 |
0 |
1 |
0 |
| c |
0 |
0 |
0 |
1 |
| d |
0 |
0 |
0 |
0 |
|
| -> |
a |
b |
c |
d |
| a |
0 |
1 |
1 |
0 |
| b |
0 |
0 |
1 |
1 |
| c |
0 |
0 |
0 |
1 |
| d |
0 |
0 |
0 |
0 |
|
| -> |
a |
b |
c |
d |
| a |
0 |
1 |
1 |
1 |
| b |
0 |
0 |
1 |
1 |
| c |
0 |
0 |
0 |
1 |
| d |
0 |
0 |
0 |
0 |
|
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
-- AndreaSterbini - 26 Mar 2002
This topic: Architetture2/MZ > DateEScadenze > PrimoProgetto2002
Topic revision: r4 - 2002-03-30 - AndreaSterbini
Copyright © 2008-2025 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback