Implémentation
Nous allons voir trois techniques pour implémenter les graphes en Python.
Afin de visualiser ces graphes, nous utiliserons le framework GraphViz. Pour automatiser la traduction entre notre implémentation et celle de GraphViz, vous devrez utiliser le fichier Python ci-dessous :
Utilisation de l'outil
Après avoir téléchargé le fichier dans le même dossier que votre programme Python, importez-le avec la commande :
from voir_graphe import *
Vous pouvez ensuite utiliser les fonctions visualiser_graphe(graphe) ou visualiser_digraphe(graphe) pour
afficher dans le navigateur respectivement les graphes non orientés et les graphes orientés, où graphe est le
graphe créé avec l'une des trois implementations ci-dessous.
Matrice d'adjacence
On utilise une matrice (un tableau à deux dimensions) pour représenter les liaisons entre les sommets du graphe. On utilise une liste de listes en Python.
Matrice d'adjacence
La matrice d'adjacence d'un graphe contient autant de lignes et de colonnes qu'il y a de sommets dans le graphe.
Chaque coefficient (chaque case du tableau) prend la valeur 0 ou 1 :
- 0 si les sommets représentés par la ligne et la colonne du coefficient ne sont pas reliés par une arête (ou un arc)
- 1 s'ils sont reliés
Exemple
graphe = [
[0, 1, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 1],
[0, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 0],
[1, 1, 0, 1, 0, 0]
]
Variante
Il existe des variantes avec lesquelles la valeur du coefficient indique le nombre d'arêtes, ou bien encore le poids de l'arête.
Listes d'adjacence
La liste d'adjacence d'une matrice indique, pour chaque sommet, avec quel autre sommet est-il relié.
Définition
La liste d'adjacence d'une matrice est une liste qui contient autant de listes que de sommet. Chaque sous-liste liste les sommets reliés au sommet décrivant la sous-liste.
Exemple
Il est impératif de décaler la numérotation des sommets pour avoir les sommets 0, 1, 2 ... (les numéros suivent les indices dans la liste).
graphe = [
[1, 5],
[0, 2, 5],
[1, 3],
[4, 5],
[3],
[0, 1, 3]
]
Dictionnaires
Les deux méthodes vues posent un problème : il est difficile de conserver le libellé des sommets. On propose donc une amélioration mixant les listes d'adjacence et les dictionnaires.
Exemple
Il est impératif de décaler la numérotation des sommets pour avoir les sommets 0, 1, 2 ... (les numéros suivent les indices dans la liste).
graphe = {
1: [2, 6],
2: [1, 3, 6],
3: [2, 4],
4: [5, 6],
5: [4],
6: [1, 2, 4]
}