PDA

Visualizza la versione completa : [?] matrici


9178angel
03-09-2004, 09:26
qualcuno mi sa dire cos' una matrice di adiacenza????

Hornwind
03-09-2004, 09:41
semplicemente un modo di rappresentare un grafo in cui gli elementi rappresentano il peso della connessione. Nei grafi non orientati si usano solo 0, 1, mentre in quelli orientati usuale trovare 0,1,-1. :ciauz:

9178angel
03-09-2004, 09:59
volendo implementare un grafo in c++ quindi la matrice mi direbbe se esiste o meno un collegamento diretto cn un nodo..giusto???

uhm cm cavolo si fa??? :dh:

Hornwind
03-09-2004, 10:05
si...
ad esempio: | 0 1 |
| 1 1 |

rappresenta il grafo:

o
/|
o o

Se invece il grafo pesato (e/o orientato) i valori ti danno il peso della connessione e l'orientamento.

:ciauz:

Hornwind
03-09-2004, 10:05
PS: Cerca di sforzarti... il post non venuto tanto bene... :bh:

9178angel
03-09-2004, 10:26
ma se la matrice 2x2 mi dice perch hai messo 3 nodi????
|0 1|
|1 1|

la prima riga dice

a-->b

la seconda
b-->a
b-->b

giusto o interpreto male la matrice???

Hornwind
03-09-2004, 10:35
il primo zero dice che non esiste collegamento tra il nodo (0,0) e tutti gli altri... quindi sconnesso dal grafo...

Hornwind
03-09-2004, 10:39
Per essere precisi:
Se tu hai un grafo con n vertici, la matrice di adiacenza ha dimensione nxn dove mat[i,j] == 1 se nel grafo esiste il lato (i,j).

9178angel
03-09-2004, 13:11
scusa proprio nn riesco a capire.... :dh: :confused:


a b c
a 0 1 0
b 0 0 1
c 1 0 0




a
/ \
/ \
\/ \/
b<----c


:master:
per favore spiegatemelo "terra terra "

un'altra cosa la calsse grafo cm verrebbe?



class grafo {

int valore; // valore del nodo
int flag[][]; // 0 se non esiste un arco 1 se esiste
grafo *next; // a seconda del valore del flag punta al nodo
}

nn credo di aver capito bene!!! :master:

da considerare che vanno inserite le funzioni vabb qs a parte

9178angel
04-09-2004, 11:08
ok ci rinuncio!!!! :dh:

Loading