La fiche de cours
Résumé en cinq points
- Un parcours visite chaque sommet accessible une fois grâce à un marquage. Avec des listes d'adjacence, il coûte O(n + m), contre O(n²) avec une matrice.
- La structure des sommets en attente fixe le parcours : une file pour la largeur, la pile d'appels récursifs pour la profondeur. Les parents forment l'arborescence du parcours et donnent un chemin depuis la source.
- Le parcours en profondeur attribue des dates de début et de fin dont les intervalles sont disjoints ou emboîtés. Le lemme du chemin blanc dit quels sommets deviennent descendants.
- Pendant l'exploration de u, un arc u → v mène à un sommet blanc, gris ou noir. Dans un graphe orienté acyclique, jamais à un sommet gris, d'où f(v) < f(u).
- Dans un graphe orienté acyclique, les dates de fin décroissantes donnent un tri topologique. Un graphe orienté admet un tri topologique si et seulement s'il est acyclique.
Pourquoi ce chapitre
Un graphe modélise un réseau, des dépendances entre tâches, les états d'un automate ou les contraintes d'un problème logique. Presque toute question sur un graphe commence par un parcours : visiter chaque sommet accessible une fois et une seule. Deux stratégies suffisent, la largeur et la profondeur. Avec des listes d'adjacence, elles coûtent un temps linéaire. Chaque application est une variation du même squelette : cycle, composantes, coloration en deux couleurs, distances, ordre des tâches. Aux concours, on attend ces parcours écrits sans hésiter, une preuve de correction par invariant et une complexité justifiée.
Fin de l'aperçu gratuit
Encore 9 parties de cours.
Fiche rédigée à partir des programmes officiels d'informatique de 2021. Pour l'option informatique de MP, elle couvre la partie 2.2 « Graphes avancés » (parcours, arborescence d'un parcours, applications). Pour MPI, elle couvre la partie 4.5 « Algorithmique des graphes » (accessibilité, tri topologique, composantes fortement connexes par l'algorithme de Kosaraju, lien avec 2-SAT) et la structure unir et trouver. Le code est en OCaml.