Passer d'une représentation d'un graphe à une autre

Pour représenter un graphe, on peut utiliser une matrice d’adjacence, dont les éléments permettent de repérer les sommets qui sont liés (valeur non nulle) ou non (valeur nulle) par un arc.

Pour représenter un graphe, on peut aussi utiliser la structure de dictionnaire avec la liste d’adjacence.

Voici les différentes représentations d’un graphe G : représentation sagittale, matrice d’adjacence et liste d’adjacence.

Représentation sagittale	Matrice d’adjacence	Liste d’adjacence
		G={'A':['B','C'], 'B':['A','C'], 'C':['A','B']}

Le choix de la représentation du graphe dépend du contexte. La matrice d’adjacence est en effet facile à lire et à interpréter par rapport à la liste d’adjacence, mais c’est la liste d’adjacence que l’on va privilégier du point de vue de la complexité temporelle (temps d’exécution).

Il y a une n² éléments dans une matrice, il faut donc tous les parcourir pour chercher une valeur. Du point de vue de la complexité temporelle (temps d’exécution), on est de l’ordre de O(n²) pour cette opération.

La structure de dictionnaire permet d’éviter cela puisqu’on accède directement à une valeur grâce à sa clé : la recherche d’une valeur dans une liste d'adjacence se fait donc en un temps constant (O(1)).

Un dictionnaire est un objet immuable. La structure de dictionnaire de la liste d’adjacence n’est donc pas adaptée à une situation où l’on doit changer ou supprimer des valeurs.

On considère le graphe G donné par sa liste d’adjacence, on a donc une structure de dictionnaire.

On connait le nombre de ses sommets, qui correspond au nombre de clés présentes dans la liste d’adjacence. On note n ce nombre.

Voici l’algorithme qui permet d’obtenir la matrice d’adjacence associée à cette liste d’adjacence.

1. Créer la liste des sommets.
2. Créer une matrice carrée A d’ordre n qui ne contient que des 0.
   Cette matrice comporte donc n lignes et n colonnes.
3. On fixe i (indice de la ligne étudiée) :
   pour parcourir les différentes colonnes, on fait prendre à j (indice de la colonne) les valeurs de 0 à n – 1 : si le sommet de la j-ème colonne est dans la liste des valeurs associées à la clé i dans la liste d’adjacence, alors A[i][j]=1 (on affecte 1 à l'élément placé à la i-ème ligne et à la j-ème colonne du tableau A).

La liste d’adjacence est notée G.

Voici ci-dessous le programme Python qui permet de passer de la liste d’adjacence G du graphe à sa matrice d’adjacence.

Voici l’explication ligne à ligne de ce code.

Le graphe est stocké à l’aide d’une matrice d’adjacence M. Les sommets sont stockés dans une liste.

Voici l’algorithme qui permet d’obtenir la liste d’adjacence associée à cette matrice d’adjacence.

1. Créer le dictionnaire vide G.
2. Obtenir le nombre de sommets du graphe.
3. Parcourir la matrice d’adjacence M ligne par ligne.
   • Sur une ligne, qui correspond donc à un sommet, créer une liste vide qui va contenir les sommets adjacents.
   • Parcourir les éléments de cette ligne en ajoutant à la liste le ou les sommets qui correspondent lorsque le coefficient vaut 1.
   • Une fois arrivé au bout de la ligne, stocker la liste comme valeur associée à la clé.

Exemple
On étudie la matrice d’adjacence du graphe G.

1. On crée le dictionnaire vide G : G={}
2. On a 3 lignes et 3 colonnes : il y a donc 3 sommets.
   On nomme par exemple ces sommets A, B et C .
3. On parcourt les éléments de chaque ligne :
   • On parcourt la première ligne, celle du sommet A :
     on ajoute les sommets qui correspondent lorsque le coefficient vaut 1. On a pour 'A' : ['B']
   • On parcourt de la même manière la deuxième ligne, celle du sommet B. On a pour 'B' : ['A','C']
   • On parcourt enfin la troisième ligne, celle du sommet C. On a pour 'C' : ['B']

On a donc la liste d’adjacence :
{'A':['B'],'B':['A','C'],'C':['B']}.

Voici ci-dessous le programme Python qui permet de passer de la matrice d’adjacence du graphe G à sa liste d’adjacence.

Voici l’explication ligne à ligne de ce code.

Exemple
Voici l’exécution de ce code sur Python Tutor pour la matrice d’adjacence :
M=[[0,1,1],[1,0,1],[1,1,0]].

On obtient le résultat suivant.

Ce résultat indique qu’à la valeur « A » on associe la liste ['B','C'], qu’à la valeur « B » on associe la liste ['A','C'] et qu’à la valeur « C », on associe la liste ['A','B'].

On obtient donc la liste d’adjacence :
{'A':['B','C'],'B':['A','C'],'C':['A','B']}.

Dans le graphe associé, les sommets A, B et C sont adjacents.