Matrice d'adjacence sommet-sommet

C'est une matrice $n\,\times\,n$ telle que $a_{ij}=1$ pour tout arc $(i,\,j)$ appartenant au graphe, tous les autres éléments étant nuls. Lorsqu'un graphe est dense, c'est à dire lorsque $m$ est proche de $n^2$, cette matrice constitue un moyen de stockage efficace au point de vue place mémoire mais elle s'avère délicate à utiliser algorithmiquement. Cette matrice s'adapte bien au cas des graphes non simples, il suffit de prendre $a_{ij}$ égal au nombre d'acrs d'origine $i$ et de destination $j$. Dans le cas non orienté, la matrice d'adjacence est symétrique. Il suffit de poser $a_{ij}$ égal au nombre d'arêtes entre $i$ et $j$.