00 — Modéliser un problème en graphe
Ce que tu vas apprendre
- Ce qu'est un graphe : sommets et arêtes
- Le vocabulaire essentiel (orienté, pondéré, cyclique, connexe)
- Pourquoi reconnaître un graphe dans un problème ouvre des solutions connues
- Le plan de la série
Prérequis
- Les séries Structures de données et Complexité aident, mais l'essentiel est rappelé ici
Beaucoup de problèmes qui semblent compliqués deviennent simples dès qu'on les voit comme des graphes. Un réseau social, des dépendances entre tâches, un plan de métro, les imports entre modules de code, les états d'un automate : tout ça, ce sont des graphes. Et le graphe est l'un des domaines les mieux outillés de l'algorithmie. Une fois ton problème modélisé en graphe, tu peux souvent appliquer un algorithme classique au lieu d'en inventer un. C'est tout l'enjeu de cette série : reconnaître les graphes, et connaître les algorithmes qui vont avec.
Sommets et arêtes
Un graphe est fait de sommets (les entités) reliés par des arêtes (les relations). C'est tout. Un réseau social : les sommets sont les personnes, les arêtes sont les amitiés. Un plan de métro : les sommets sont les stations, les arêtes sont les tronçons. Un projet : les sommets sont les tâches, les arêtes sont les dépendances « doit finir avant ».
Un graphe simple à 4 sommets :
A —— B
| / |
| / |
C —— D
Sommets : A, B, C, D
Arêtes : A-B, A-C, B-C, B-D, C-DCette abstraction est extrêmement générale, et c'est sa force. Le même algorithme de plus court chemin sert à calculer un itinéraire GPS, le nombre de degrés de séparation entre deux personnes, ou le coût minimal de transformation d'un mot en un autre.
Le vocabulaire essentiel
Les graphes se déclinent selon quelques propriétés qui déterminent quels algorithmes s'appliquent.
Orienté ou non orienté. Dans un graphe non orienté, une arête A-B se parcourt dans les deux sens (une amitié est réciproque). Dans un graphe orienté, une arête a un sens : A→B ne donne pas B→A (un compte qui en suit un autre, une dépendance « A nécessite B »).
Pondéré ou non pondéré. Une arête peut porter un poids : une distance, un coût, une durée. Le plus court chemin sur un graphe non pondéré (compter les arêtes) et sur un graphe pondéré (minimiser la somme des poids) demandent des algorithmes différents, BFS dans un cas, Dijkstra dans l'autre.
Cyclique ou acyclique. Un cycle est un chemin qui revient à son point de départ. Un graphe orienté sans cycle s'appelle un DAG (Directed Acyclic Graph), une structure très importante : c'est ce qui permet d'ordonner des dépendances, comme on le verra avec le tri topologique.
Connexe. Un graphe est connexe si on peut atteindre n'importe quel sommet depuis n'importe quel autre. Sinon, il se découpe en composantes connexes (des îlots séparés). La structure union-find de la série précédente sert justement à tester la connexité.
| Propriété | Question | Exemple |
|---|---|---|
| Orienté | la relation a-t-elle un sens ? | suivre un compte (oui), amitié (non) |
| Pondéré | les arêtes ont-elles un coût ? | distance routière (oui) |
| Acyclique (DAG) | peut-on revenir au départ ? | dépendances de build (non = DAG) |
| Connexe | tout est-il relié ? | réseau fragmenté ou non |
Reconnaître un graphe dans un problème
Le savoir-faire central de cette série n'est pas d'implémenter les algorithmes (les bibliothèques le font souvent), mais de voir qu'un problème est un problème de graphe. Quelques signaux :
- des entités reliées par des relations (« qui connaît qui », « quoi dépend de quoi ») ;
- une question de chemin (« peut-on aller de X à Y ? », « quel est le plus court ? ») ;
- une question d'ordre sous contraintes (« dans quel ordre exécuter ces tâches ? ») ;
- une question de regroupement (« combien d'îlots séparés ? »).
Dès que l'un de ces signaux apparaît, modélise en sommets et arêtes, et un algorithme classique attend probablement.
Le plan de la série
| Article | Contenu |
|---|---|
| 00 — Introduction | Modéliser en graphe (cet article) |
| 01 — Représentation | Liste vs matrice d'adjacence, coûts |
| 02 — Parcours en largeur (BFS) | Plus court chemin non pondéré |
| 03 — Parcours en profondeur (DFS) | Récursion, pile, applications |
| 04 — Détection de cycle et DAG | Graphes acycliques |
| 05 — Tri topologique | Ordonner des dépendances |
| 06 — Dijkstra | Plus court chemin pondéré |
| 07 — Bellman-Ford et A* | Poids négatifs, heuristique |
| 08 — En pratique | Graphes dans le vrai code |
L'article suivant pose la première brique technique : comment représenter un graphe en mémoire, et pourquoi ce choix change la complexité de tous les algorithmes qui suivent.
Sources
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (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.
- Skiena, S. S. (2008). The Algorithm Design Manual (2nd ed.), Chapitre 5 "Graph Traversal". Springer.