Matrice delle adiacenze
Da Wikipedia, l'enciclopedia libera.
La matrice delle adiacenze costituisce una particolare struttura dati comunemente utilizzata nella rappresentazione dei grafi. In particolare è ampiamente utilizzata nella stesura di algoritmi che operano su grafi e in generale nella loro rappresentazione informatica.
Dato un qualsiasi grafo orientato la sua matrice delle adiacenze è costituita da una matrice binaria quadrata che ha come indici di righe e colonne i nomi dei vertici del grafo. Nel posto (i,j) della matrice si trova un 1 se e solo se esiste nel grafo un arco che va dal vertice i al vertice j, altrimenti si trova uno 0.
Notare come A e B siano connessi nei due sensi, e quindi abbiamo un 1 sia nel posto (A,B) che in (B,A), con degli 1 simmetrici rispetto alla diagonale della matrice. L'arco (B,C) va solo da B a C e non viceversa: infatti non vi è un 1 simmetrico nel posto (C,B). Infine C presenta un autoanello, quindi sulla diagonale al posto (C,C) c'è un 1 (si può andare da C a C)
Se al posto degli 1 nella matrice si trovano dei numeri, questi sono da interpretare come il peso attribuito a ciascun arco. Ad esempio se l'insieme dei vertici del grafo rappresenta una serie di punti su una cartina geografica, il peso degli archi può essere interpretato come la distanza dei punti che questi connettono.
