Représentations d'un graphe

Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d'adjacence, listes des voisins, des successeurs ou des prédécesseurs.

IMatrice d'adjacence

Une matrice est un tableau de nombres. Elle peut être représentée en machine simplement par une liste de listes. Si on note mat une matrice, l'élément qui est en $i$-ième ligne et en $j$-ième colonne est accessible en Python à l'aide de mat[i][j].

Un graphe peut être représenté par une matrice d'adjacence : s'il y a un lien depuis le sommet $i$ vers le sommet $j$, on pose mat[i][j] = 1 et si il n'y en a pas on pose mat[i][j] = 0. Exemple : graphes et leur matrice d'adjacence.

Lorsqu'un graphe est non orienté sa matrice d'adjacence est symétrique : on a toujours $m_{i,j}=m_{j,i}$.

Exemple d'une classe GrapheM s'appuyant sur la représentation par matrice d'adjacence (g1 et g2 correspondent aux graphes 1 et 2 ci-dessus) :

IIListe des voisins

Pour représenter un graphe, on peut également, pour chacun de ses sommets, donner la liste des sommets auxquels il est relié. Lorsque le graphe est non orienté, on parle de liste de voisins. Lorsqu'il est orienté, on peut décider de représenter un graphe par la liste de ses successeurs ou, lorsque les problèmes que l'on étudie rendent cette représentation plus adaptée, par la liste de ses prédécesseurs.

Nous choisirons de coder ici les sommets avec des nombres (de 0 à $n-1$, où $n$ est l'ordre du graphe) et les listes de successeurs avec des listes, ce qui facilite le passage d'une liste de voisins à la matrice d'adjacence. Il est également possible de coder les listes de successeurs avec des dictionnaires, ce qui permet d'étiqueter les graphes.

Voici un exemple de classe simple implémentant la représentation par liste de successeurs (g3 et g4 correspondent aux graphes 1 et 2 précédents) :