01 — Représenter un graphe : liste vs matrice d'adjacence
Ce que tu vas apprendre
- Les deux représentations principales d'un graphe
- Leurs coûts en mémoire et pour les opérations de base
- Comment la densité du graphe décide du bon choix
- Le code de référence utilisé dans le reste de la série
Prérequis
Avant tout algorithme, il faut stocker le graphe en mémoire. Ce choix de représentation n'est pas un détail : il fixe la complexité de toutes les opérations qui suivront. Deux représentations dominent, la liste d'adjacence et la matrice d'adjacence. Le bon choix dépend d'une propriété du graphe, sa densité.
La liste d'adjacence
Pour chaque sommet, on stocke la liste de ses voisins. C'est une table (souvent une Map ou un tableau de tableaux) qui associe à chaque sommet ses connexions.
typescript// graphe non orienté : A-B, A-C, B-D
const graphe = new Map<string, string[]>([
["A", ["B", "C"]],
["B", ["A", "D"]],
["C", ["A"]],
["D", ["B"]],
]);
// parcourir les voisins de A
for (const voisin of graphe.get("A") ?? []) {
// ...
}
pythongraphe = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A"],
"D": ["B"],
}
La mémoire utilisée est proportionnelle au nombre de sommets plus le nombre d'arêtes : O(V + E), où V est le nombre de sommets et E le nombre d'arêtes. On ne stocke que les connexions qui existent réellement. Parcourir tous les voisins d'un sommet est immédiat. En revanche, tester si une arête précise existe (« A et D sont-ils reliés ? ») demande de parcourir la liste des voisins de A, en O(degré du sommet).
La matrice d'adjacence
On utilise une matrice V × V, où la case [i][j] vaut 1 (ou le poids) s'il existe une arête de i vers j, et 0 sinon.
python# 4 sommets indexés 0..3, arêtes 0-1, 0-2, 1-3
n = 4
M = [[0] * n for _ in range(n)]
def ajouter_arete(a, b):
M[a][b] = 1
M[b][a] = 1 # non orienté : symétrique
ajouter_arete(0, 1)
ajouter_arete(0, 2)
ajouter_arete(1, 3)
# tester une arête : O(1)
existe = M[0][1] == 1
L'avantage est le test d'arête en O(1) : une seule lecture de case. Le défaut est la mémoire : la matrice occupe toujours O(V²), qu'il y ait beaucoup d'arêtes ou très peu. Et parcourir les voisins d'un sommet coûte O(V), car il faut balayer toute une ligne, même si le sommet n'a que deux voisins.
Le choix : la densité décide
Tout se joue sur la densité, soit le rapport entre le nombre d'arêtes réel et le maximum possible.
Un graphe creux (sparse) a peu d'arêtes par rapport aux sommets. C'est le cas le plus fréquent dans le monde réel : un réseau social où chacun a quelques centaines de contacts parmi des millions d'utilisateurs, un graphe de dépendances où chaque module en importe quelques-uns. Pour ces graphes, la liste d'adjacence est bien plus économe : O(V + E) au lieu de O(V²).
Un graphe dense a presque toutes les arêtes possibles. Là, la matrice se justifie : la mémoire O(V²) n'est plus du gâchis, et le test d'arête en O(1) devient un vrai avantage.
| Critère | Liste d'adjacence | Matrice d'adjacence |
|---|---|---|
| Mémoire | O(V + E) | O(V²) |
| Tester une arête (u, v) | O(degré de u) | O(1) |
| Parcourir les voisins de u | O(degré de u) | O(V) |
| Adapté aux graphes | creux | denses |
En pratique, la grande majorité des graphes réels sont creux, et la liste d'adjacence est le choix par défaut. C'est elle qu'on utilisera dans le reste de la série, et c'est ce qui rend les complexités des algorithmes à venir en O(V + E) plutôt qu'en O(V²).
Représenter les poids
Pour un graphe pondéré (article 06, Dijkstra), on adapte légèrement. Avec une liste d'adjacence, chaque voisin est un couple (sommet, poids).
python# graphe pondéré : arête A->B de poids 5
graphe = {
"A": [("B", 5), ("C", 2)],
"B": [("D", 1)],
"C": [("B", 3)],
"D": [],
}
Avec une matrice, la case contient directement le poids (et une valeur spéciale, par exemple l'infini, pour l'absence d'arête).
Le choix de représentation étant posé, l'article suivant attaque le premier algorithme de parcours, celui qui visite un graphe niveau par niveau et résout le plus court chemin non pondéré : le parcours en largeur.
Sources
- Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 22.1 "Representations of Graphs". MIT Press.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 4.1. Addison-Wesley.
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Section 5.2 "Data Structures for Graphs". Springer.