Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
les_programmes_a_connaitre:structure_de_donnees_term:implementation_graphe_adjascence [2021/01/26 10:30] sn |
les_programmes_a_connaitre:structure_de_donnees_term:implementation_graphe_adjascence [2021/01/26 10:40] (Version actuelle) sn |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
+ | |||
Il existe plusieurs méthodes permettant d' | Il existe plusieurs méthodes permettant d' | ||
Une matrice est un **tableau à double entrée** | Une matrice est un **tableau à double entrée** | ||
- | Cependant, voici à quoi ressemble une matrice d' | + | Voici donc à quoi ressemble une matrice d' |
+ | |||
+ | 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' | ||
+ | |||
+ | 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' | ||
+ | Il n' |