[?] matrici

[9178angel]

qualcuno mi sa dire cos'è una matrice di adiacenza????

[Hornwind]

è 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.

[9178angel]

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???

[Hornwind]

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.

[Hornwind]

PS: Cerca di sforzarti... il post non è venuto tanto bene...

[9178angel]

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]

il primo zero dice che non esiste collegamento tra il nodo (0,0) e tutti gli altri... quindi è sconnesso dal grafo...

[Hornwind]

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]

scusa proprio nn riesco a capire....

 
  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]

ok ci rinuncio!!!!