backend / algorithmes-structures-donnees
Graphes : représentations
Explication
Ce que vous allez apprendre
- Modéliser un problème réel (réseau, carte, dépendances) en sommets et arêtes
- Comparer liste d'adjacence et matrice d'adjacence selon la mémoire consommée et le coût d'un test d'existence d'arête
- Justifier pourquoi la liste d'adjacence est préférée pour les graphes creux, majoritaires dans le monde réel
- Distinguer graphe orienté / non orienté et graphe pondéré / non pondéré
- Choisir la bonne représentation avant même d'implémenter un algorithme de parcours ou de plus court chemin
Dans quel contexte ?
Une application de réseau social doit stocker les relations "suit" entre 10 millions d'utilisateurs, sachant que chaque utilisateur suit en moyenne 150 comptes. Une matrice d'adjacence nécessiterait 10 millions au carré cases, soit 100 000 milliards d'entrées : totalement impraticable. Une liste d'adjacence, elle, ne stocke que les relations qui existent réellement, soit environ 1,5 milliard d'entrées, cent mille fois moins. C'est ce choix de représentation, fait avant même d'écrire le premier algorithme de parcours, qui détermine si le système tient en mémoire ou non.
D'abord, un nouveau type de problème à modéliser
Toutes les structures vues jusqu'ici organisaient des collections ou des hiérarchies. Un plan de métro, un réseau social, une carte routière ont un point commun : ce sont des relations quelconques entre entités, sans hiérarchie stricte. C'est exactement ce qu'un graphe modélise, avec des sommets (les entités) reliés par des arêtes (les relations).
Prérequis
V désigne le nombre de sommets (vertices) et E le nombre d'arêtes (edges) — cette notation revient dans toute la suite du cours sur les graphes.
La question à régler avant tout le reste
Avant même de parcourir ou d'analyser un graphe, il faut choisir comment le représenter en mémoire. Ce choix a des conséquences directes sur la performance de tous les algorithmes qui suivront.
Étape 1 : la liste d'adjacence
Cette représentation associe à chaque sommet la liste de ses voisins directs. Elle est économe en mémoire, proportionnelle au nombre réel d'arêtes, ce qui la rend idéale pour les graphes creux — la grande majorité des graphes du monde réel, où chaque sommet n'est connecté qu'à une poignée d'autres.
Étape 2 : la matrice d'adjacence, l'approche inverse
Cette représentation réserve une case pour CHAQUE paire possible de sommets, qu'une arête existe ou non entre eux. Elle consomme O(V²) de mémoire, même si le graphe est presque vide.
| Représentation | Mémoire | Test d'existence d'une arête | Idéal pour |
|---|---|---|---|
| Liste d'adjacence | O(V + E) | O(degré du sommet) | Graphes creux (la majorité des cas réels) |
| Matrice d'adjacence | O(V²) | O(1) | Graphes denses, petits graphes |
Piège fréquent
Utiliser une matrice d'adjacence par réflexe, sans vérifier la densité réelle du graphe, peut faire exploser la mémoire consommée sur un grand graphe creux. Vérifiez toujours l'ordre de grandeur de V avant de choisir : au-delà de quelques milliers de sommets, la liste d'adjacence s'impose presque toujours.
Le compromis entre ces deux approches
En échange de cette consommation mémoire plus élevée, la matrice offre un test d'existence d'une arête en O(1) instantané. La liste d'adjacence, elle, doit parcourir la liste des voisins pour répondre à la même question.
Pourquoi ce choix a un vrai impact pratique
Un parcours sur une liste d'adjacence explore les voisins d'un sommet en temps proportionnel à son degré réel. Le même parcours sur une matrice doit scanner toute une ligne de taille V, même si le sommet n'a que deux voisins réels : sur un graphe creux, cette différence devient déterminante.
Une dernière distinction à connaître
Un graphe non orienté duplique chaque relation dans les deux sens ; un graphe orienté ne la stocke que dans le sens où elle existe réellement. Ajouter un poids à chaque arête transforme un simple graphe de connectivité en un graphe capable de représenter des problèmes d'optimisation.
Vers la suite
Une fois un graphe représenté en mémoire, la question naturelle devient : comment le parcourir pour visiter tous ses sommets ? C'est le sujet de la prochaine leçon, sur BFS et DFS.
Commandes & code
Graphes : représentations
# --- Liste d'adjacence : la représentation la plus courante, économe en mémoire pour graphe creux ---
class GrapheListeAdjacence:
def __init__(self, oriente: bool = False):
self.oriente = oriente
self.adjacence: dict[str, list[tuple[str, float]]] = {}
def ajouter_sommet(self, sommet: str) -> None:
self.adjacence.setdefault(sommet, [])
def ajouter_arete(self, a: str, b: str, poids: float = 1.0) -> None:
# O(1) amorti
self.ajouter_sommet(a)
self.ajouter_sommet(b)
self.adjacence[a].append((b, poids))
if not self.oriente:
self.adjacence[b].append((a, poids))
def voisins(self, sommet: str) -> list[tuple[str, float]]:
return self.adjacence.get(sommet, [])
def a_arete(self, a: str, b: str) -> bool:
# O(deg(a)) : il faut parcourir la liste des voisins de a
return any(voisin == b for voisin, _ in self.adjacence.get(a, []))
g = GrapheListeAdjacence()
g.ajouter_arete("A", "B", 4)
g.ajouter_arete("A", "C", 1)
g.ajouter_arete("C", "B", 2)
assert g.a_arete("A", "B") is True
assert g.voisins("A") == [("B", 4), ("C", 1)]
# --- Matrice d'adjacence : O(1) pour tester une arête, O(n^2) en mémoire ---
class GrapheMatriceAdjacence:
def __init__(self, sommets: list[str], oriente: bool = False):
self.oriente = oriente
self.index = {s: i for i, s in enumerate(sommets)}
self.sommets = sommets
n = len(sommets)
self.matrice = [[0.0] * n for _ in range(n)] # 0 = pas d'arête, float = poids
def ajouter_arete(self, a: str, b: str, poids: float = 1.0) -> None:
i, j = self.index[a], self.index[b]
self.matrice[i][j] = poids
if not self.oriente:
self.matrice[j][i] = poids
def a_arete(self, a: str, b: str) -> bool:
# O(1) -- accès direct dans la matrice, contrairement à la liste d'adjacence
return self.matrice[self.index[a]][self.index[b]] != 0
m = GrapheMatriceAdjacence(["A", "B", "C"])
m.ajouter_arete("A", "B", 4)
assert m.a_arete("A", "B") is True
assert m.a_arete("B", "C") is False
# --- Graphe orienté pondéré : représentation pour Dijkstra / topological sort ---
graphe_oriente = GrapheListeAdjacence(oriente=True)
graphe_oriente.ajouter_arete("depart", "A", 2)
graphe_oriente.ajouter_arete("A", "arrivee", 3)
graphe_oriente.ajouter_arete("depart", "arrivee", 10)
# --- Liste d'arêtes : format compact, utile pour Kruskal (tri global des arêtes) ---
liste_aretes: list[tuple[float, str, str]] = [
(4, "A", "B"),
(1, "A", "C"),
(2, "C", "B"),
]
liste_aretes.sort() # tri par poids -- première étape de l'algorithme de Kruskal
# Comparaison des représentations
# Liste d'adjacence : espace O(V + E), a_arete O(deg), idéale pour graphe CREUX (peu d'arêtes)
# Matrice d'adjacence : espace O(V^2), a_arete O(1), idéale pour graphe DENSE ou petit nombre de sommetsRésumé
- Liste d'adjacence : O(V + E) en mémoire, adaptée aux graphes creux (la majorité des cas réels).
- Matrice d'adjacence : O(V^2) en mémoire, test d'arête en O(1), adaptée aux graphes denses ou de petite taille.
- Liste d'arêtes : format compact utile pour les algorithmes qui trient globalement les arêtes (Kruskal).
- Un graphe orienté stocke l'arête dans un seul sens ; un graphe non orienté la duplique dans les deux listes d'adjacence.
Exercices pratiques
Mission : sauver la mémoire du serveur qui stocke le réseau social
Objectif : Justifier un choix de représentation de graphe par calcul, puis implémenter la représentation adaptée.
Contexte
Un serveur doit stocker le graphe des relations "suit" pour 2 millions d'utilisateurs, sachant que chaque utilisateur suit en moyenne 200 comptes. Un développeur a choisi une matrice d'adjacence "pour avoir un test d'arête instantané", et le serveur tombe en panne mémoire au démarrage.