Wiki NSI

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.


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:{{:les_programmes_a_connaitre:structure_de_donnees_term:matrice.png?100|}}

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: {{:les_programmes_a_connaitre:structure_de_donnees_term:carte_matrice.png?200|}}

Sa matrice ressemble à ça: {{:les_programmes_a_connaitre:structure_de_donnees_term:matrice_de_la_carte.png?400|}}

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