08 — Les graphes dans le vrai code

Ce que tu vas apprendre

• Comment reconnaître un graphe déguisé dans un problème courant
• Trois cas réels résolus avec les algorithmes de la série
• Une grille pour choisir l'algorithme
• Ce que tout le parcours algorithmie t'a apporté

Prérequis

• L'ensemble de la série, des parcours aux plus courts chemins

On a vu la théorie : représentation, parcours, cycles, ordonnancement, plus courts chemins. Cet article fait le pont avec le code que tu écris vraiment. Le plus dur avec les graphes n'est pas d'implémenter les algorithmes, c'est de reconnaître qu'un problème en est un. Une fois la modélisation faite, l'algorithme adapté est presque toujours l'un de ceux de cette série.

Reconnaître un graphe déguisé

Les graphes se cachent derrière des formulations qui n'évoquent ni « sommet » ni « arête ». Voici des indices qui doivent te faire penser graphe.

• « Qui peut atteindre quoi », « est-ce relié », « combien de groupes séparés » → connexité, BFS/DFS, union-find.
• « Dans quel ordre, en respectant les dépendances » → DAG et tri topologique.
• « Le plus court / le moins cher / le plus rapide chemin » → BFS, Dijkstra ou A* selon les poids.
• « Y a-t-il une boucle, une dépendance circulaire » → détection de cycle.
• « De combien d'étapes suis-je de… » → BFS.

Le réflexe à construire : identifier les entités (les sommets) et les relations (les arêtes), puis poser la question dans le vocabulaire des graphes. Le problème se range alors presque toujours dans une case connue.

Cas 1 : détecter une dépendance circulaire entre modules

Le besoin : un outil de build doit vérifier que les modules ne s'importent pas en cercle (A importe B, B importe C, C importe A), ce qui rendrait l'ordre de chargement impossible.

Modélisation : les modules sont les sommets, « A importe B » est une arête orientée A→B. La question « y a-t-il une dépendance circulaire ? » devient « ce graphe orienté a-t-il un cycle ? ». On applique la détection de cycle par coloration (article 04). Et si on veut en plus l'ordre de chargement, le tri topologique (article 05) le donne, en signalant un cycle s'il échoue à ordonner tous les modules.

python# modules : dict module -> liste des modules importés
def ordre_de_chargement(imports):
    return tri_topologique_kahn(imports)  # lève une erreur si cycle

C'est exactement ce que font les bundlers et les gestionnaires de modules.

Cas 2 : les degrés de séparation dans un réseau

Le besoin : sur une plateforme sociale, afficher « à quelle distance » se trouve un autre utilisateur (ami, ami d'ami, etc.).

Modélisation : les utilisateurs sont les sommets, les relations d'amitié sont des arêtes non orientées et non pondérées. La question « combien d'intermédiaires entre X et Y ? » est un plus court chemin non pondéré. C'est BFS (article 02), qui donne la distance minimale en nombre d'arêtes depuis X.

pythondef degres_de_separation(reseau, moi, autre):
    chemin = plus_court_chemin(reseau, moi, autre)  # BFS
    return len(chemin) - 1 if chemin else None      # nombre d'arêtes

Le même BFS calcule, en une passe depuis un sommet, les distances vers tous les autres : utile pour « suggérer des amis à 2 degrés ».

Cas 3 : un itinéraire avec temps de trajet

Le besoin : calculer le trajet le plus rapide entre deux points d'un réseau routier, où chaque tronçon a une durée.

Modélisation : les intersections sont les sommets, les tronçons sont des arêtes pondérées par la durée. Comme les durées sont positives, c'est Dijkstra (article 06). Et si on dispose d'une estimation de la distance restante à vol d'oiseau, A* (article 07) trouve le même résultat en explorant beaucoup moins, ce qui compte sur un réseau de millions d'intersections.

Le choix entre Dijkstra et A* illustre une leçon de tout le parcours : le bon algorithme dépend de ce qu'on sait du problème. Sans information sur la destination, Dijkstra. Avec une bonne heuristique, A*.

La grille de choix

Cette grille couvre l'immense majorité des problèmes de graphes du quotidien d'un développeur.

Conclusion du parcours algorithmie

Cette série clôt un parcours commencé avec la série Complexité. Le fil est resté le même d'un bout à l'autre. La complexité a donné le langage pour mesurer le coût. Le tri a montré ce langage à l'œuvre sur des algorithmes concrets. La recherche a fourni les patterns pour éviter les O(n²) inutiles. Les structures de données ont construit les outils dont chaque profil de coûts répond à un besoin. Les graphes, enfin, ont assemblé tout ça : ils utilisent les files, les piles, les files de priorité et union-find des structures, ils s'analysent avec la complexité, et ils résolvent des problèmes que rien d'autre ne modélise aussi bien.

L'objectif n'a jamais été de te faire réimplémenter ces algorithmes en production, où les bibliothèques font le travail. Il était de te donner les yeux pour reconnaître, dans un problème concret, la structure ou l'algorithme qui le résout proprement, au lieu de partir sur la première solution naïve. C'est ce regard qui distingue un code qui marche aujourd'hui d'un code qui tiendra quand les données auront grossi.

Sources

• Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Chapitres 5 et 6, et le "Catalog of Algorithmic Problems". Springer.
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Partie VI "Graph Algorithms". MIT Press.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Chapitre 4 "Graphs". Addison-Wesley.
• Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press. (Graphes appliqués aux réseaux réels)