Wiki NSI

Il existe plusieurs méthodes permettant d'implémenter un graphe. L'une d'elle est ce qu'on appelle une matrice d'adjacence.

Une matrice est un tableau à double entrée

Voici donc à quoi ressemble une matrice d'adjacence:

Peut-être que cela fait peur au premier abord mais finalement, ce n'est pas très compliqué à comprendre.

Pour construire ce genre de matrice, il faut savoir qu'à chaque ligne correspond un sommet du graphe et qu'à chaque colonne correspond aussi un sommet du graphe. À chaque intersection ligne i-colonne j (ligne i correspond au sommet i et colonne j correspond au sommet j), on place un 1 s'il existe une arête entre le sommet i et le sommet j, et un zéro s'il n'existe pas d'arête entre le sommet i et le sommet j.

Prenons pour exemple cette carte:

Sa matrice ressemble à ça:

Ici, il existe une arête entre le sommet E et le sommet F, nous avons donc placé un 1 à l'intersection de la ligne E et de la colonne F.
Il n'existe pas d'arête entre le sommet D et le sommet C, nous avons donc placé un 0 à l'intersection de la ligne D et de la colonne C