Implémentation
Nous allons voir trois techniques pour implémenter les graphes en Python.
Matrice d'adjacence
On utilise une matrice (comprenez un tableau à deux dimensions) pour représenter les liaisons entre les sommets du graphe. On utilise une liste de listes en Python.
Définition :
La matrice d'adjacence d'un graphe contient autant de lignes et de colonnes qu'il y a de sommets dans le graphe.
Chaque coefficiant (chaque case du tableau) prend la valeur 0 ou 1 :
0 si les sommets représentés par la ligne et la colonne du coefficiant ne sont pas reliés par une arête (ou un arc)
1 s'ils sont reliés
Exemple :
1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 0 | 0 | 1 |
2 | 1 | 0 | 1 | 0 | 0 | 1 |
3 | 0 | 1 | 0 | 1 | 0 | 0 |
4 | 0 | 0 | 1 | 0 | 1 | 1 |
5 | 0 | 0 | 0 | 1 | 0 | 0 |
6 | 1 | 1 | 0 | 1 | 0 | 0 |
Complément : Variante
Il existe des variantes où la valeur du coefficiant 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 il est relié.
Définition :
La liste d'adjacence d'un graphe 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]
]
Dictionnaire
Les deux méthodes vues posent un problème : il est difficile de conserver le libbelé des sommets. On propose donc un amélioration utilisant les listes d'adjacence et les dictionnaires.
Exemple :
graphe = {
1: [2, 6],
2: [1, 3, 6],
3: [2, 4],
4: [5, 6],
5: [4],
6: [1, 2, 4]
}
Liste d'arêtes
Sur certains algorithmes, par exemple celui de Bellman-Ford, on préfére regarder le graphe comme une liste d'arêtes.
Définition :
La liste d'arête d'un graphe est une liste qui contient autant d'éléments que le graphe comporte d'arêtes. Chaque élément est alors un tuple de sommet, où le premier est la source de l'arête et le second la destination.
Exemple :
graphe = [
(1, 2),
(1, 6),
(2, 1),
(2, 3),
(2, 6),
(3, 2),
(3, 4),
(4, 3),
(4, 5),
(4, 6),
(5, 4),
(6, 1),
(6, 2),
(6, 4)
]