Programme en vigueur — arrêtés du 19 juillet 2019, applicable en Terminale depuis la rentrée 2020. Voir le texte
Graphe non-orienté et orienté. Matrice d'adjacence et liste d'adjacence. Parcours : BFS (file) et DFS (pile/récursion). Algorithme de Dijkstra : plus court chemin pondéré. Cycles et connexité.
La règle d'or
Seul le parcours en largeur, qui utilise une file, donne le plus court chemin en nombre d'arêtes ; celui en profondeur ne garantit rien.
L'erreur que tout le monde fait
Utiliser un parcours en profondeur pour déterminer la plus courte distance entre deux sommets.
La profondeur s'enfonce dans une branche jusqu'au bout avant de revenir : le premier chemin qu'elle trouve vers la cible peut faire un long détour, alors qu'un chemin direct existait dans une autre branche. La largeur, elle, explore par cercles concentriques et atteint donc chaque sommet par le plus petit nombre d'arêtes.
Retenir le couple structure-résultat : file et plus court chemin en arêtes, pile et exploration exhaustive.
Deux parcours de graphe visitent exactement les mêmes sommets, et un seul donne au passage le plus court chemin. La différence tient à une structure : une file plutôt qu'une pile.
1Représenter un graphe
Définition
Graphe — Un graphe est un ensemble de sommets reliés par des arêtes. Il est non orienté si la relation est réciproque, orienté si elle ne l'est pas — on parle alors d'arcs. Un graphe est pondéré si ses arêtes portent un poids. Deux notions à connaître : la connexité — peut-on aller de tout sommet à tout autre ? — et le cycle — existe-t-il un chemin qui revient à son point de départ ?
Propriété
Deux représentations coexistent, et le choix dépend de la densité. La matrice d'adjacence est un tableau à deux dimensions où la case (i, j) indique s'il existe une arête : le test d'adjacence est en O(1), mais l'espace occupé est en n² même si le graphe a peu d'arêtes. La liste d'adjacence associe à chaque sommet la liste de ses voisins : l'espace est proportionnel au nombre d'arêtes, et le test d'adjacence coûte davantage.
La règle pratique tient en une phrase : un graphe dense — beaucoup d'arêtes par rapport au nombre de sommets — se représente bien par une matrice d'adjacence ; un graphe creux par une liste d'adjacence. Un réseau social, où chacun connaît une poignée de personnes sur des millions, est extrêmement creux : une matrice y gaspillerait un espace considérable pour stocker presque uniquement des zéros.
2Les deux parcours
Règle
Les deux parcours visitent tous les sommets atteignables et ne diffèrent que par la structure qui mémorise les sommets à traiter. Le BFS — parcours en largeur — emploie une file : il explore les voisins immédiats, puis leurs voisins, couche par couche. Le DFS — parcours en profondeur — emploie une pile, ou la récursivité : il s'enfonce aussi loin que possible avant de revenir en arrière. Dans les deux cas, il faut marquer les sommets visités, faute de quoi un cycle provoque une boucle infinie.
Utiliser un parcours en profondeur pour déterminer la plus courte distance entre deux sommets.
Pourquoi — Le DFS trouve un chemin, sans aucune garantie sur sa longueur : il s'engage dans la première direction disponible et peut faire un immense détour avant d'atteindre un sommet voisin du départ. Seul le BFS explore couche par couche, si bien que le premier moment où il atteint un sommet correspond nécessairement au plus petit nombre d'arêtes. Le programme ne signale rien : il renvoie un chemin, simplement pas le plus court.
Le réflexe — Plus court chemin en nombre d'arêtes : BFS, donc une file.
Cette garantie du BFS vaut pour le nombre d'arêtes, c'est-à-dire pour un graphe non pondéré, ou dont toutes les arêtes coûtent la même chose. Dès que les arêtes portent des poids différents, le chemin le plus court en nombre d'arêtes n'est plus forcément le moins coûteux : il faut alors Dijkstra.
3Dijkstra
Propriété
L'algorithme de Dijkstra calcule le plus court chemin dans un graphe pondéré à poids positifs. Il maintient pour chaque sommet la meilleure distance connue, traite à chaque étape le sommet non traité le plus proche, et met à jour ses voisins. C'est une généralisation du BFS : si toutes les arêtes valent 1, les deux algorithmes traitent les sommets dans le même ordre.
La condition de positivité n'est pas une formalité. Dijkstrafige la distance d'un sommet dès qu'il le traite, en supposant qu'aucun chemin ultérieur ne fera mieux. Avec un poids négatif, un détour peut réduire la distance après coup : l'hypothèse tombe, et l'algorithme renvoie un résultat faux sans le signaler.
Programmer un parcours de graphe
Choisir la représentation selon la densité : matrice d'adjacence si dense, liste sinon.
Déterminer l'objectif : visiter tous les sommets, tester la connexité, ou trouver le plus court chemin ?
Choisir la structure en conséquence : file pour le BFS, pile ou récursion pour le DFS.Le plus court chemin en nombre d'arêtes impose le BFS.
Prévoir un ensemble de sommets visités et le consulter avant tout empilement — sinon un cycle boucle.
Pour reconstituer un chemin, mémoriser le prédécesseur de chaque sommet au moment où on l'atteint.
▢Ai-je choisi la représentation selon la densité du graphe ?
▢Ai-je marqué les sommets visités avant de les empiler ?
▢Pour un plus court chemin, ai-je bien employé une file — donc le BFS ?
▢Mon graphe est-il pondéré ? Alors Dijkstra, pas BFS.
▢Mes poids sont-ils positifs avant d'appliquer Dijkstra ?
▢Ai-je mémorisé les prédécesseurs si je dois reconstituer le chemin ?
L'essentiel en 11 points
·Graphe : sommets et arêtes ; orienté ou non, pondéré ou non.
·Connexité : va-t-on de tout sommet à tout autre ? Cycle : retour au départ.
·Matrice d'adjacence : test O(1), espace n². Liste : espace proportionnel aux arêtes.
·Graphe dense → matrice ; graphe creux → liste d'adjacence.
·BFS : une file, exploration couche par couche.
·DFS : une pile ou la récursion, en profondeur d'abord.
·Seul le BFS donne le plus court chemin en nombre d'arêtes.
·Cette garantie ne vaut que sur un graphe non pondéré.
·Graphe pondéré à poids positifs : Dijkstra.
·Toujours marquer les sommets visités, sinon un cycle boucle.
·Mémoriser les prédécesseurs pour reconstituer un chemin.
2
Imprimer
Fiche PDF — Graphes — Structures et algorithmes de parcours
Gratuit · sans compte
Trois documents à imprimer, 6 pages en tout : le cours, les exercices avec la place pour écrire, et le corrigé détaillé avec son barème.
a.Différencier graphe orienté et non orienté. Qu'est-ce que la connexité ?
b.Comparer matrice d'adjacence et liste d'adjacence.
c.Quelle structure emploie le BFS ? Le DFS ?
d.Lequel des deux donne le plus court chemin, et sous quelle condition ?
e.Que calcule Dijkstra, et sous quelle condition ?
›Voir le corrigéMasquer le corrigé
a. Le graphe orienté a des relations non réciproques — des arcs. La connexité est la possibilité d'aller de tout sommet à tout autre.
b. La matrice d'adjacence teste l'adjacence en O(1) mais occupe n² ; la liste d'adjacence occupe un espace proportionnel au nombre d'arêtes.
c. Le BFS une file ; le DFS une pile ou la récursivité.
d. Le BFS, à condition que le graphe soit non pondéré — ou que toutes les arêtes coûtent la même chose.
e. Le plus court chemin dans un graphe pondéré, à condition que les poids soient positifs.
2
Un développeur cherche la plus courte distance entre deux sommets d'un réseau non pondéré et emploie un parcours en profondeur. Analyser.
Analyser
a.Le programme va-t-il trouver un chemin ?
b.Ce chemin sera-t-il le plus court ? Pourquoi ?
c.Pourquoi le BFS garantit-il le contraire ?
d.Quelle modification minimale corrige le programme ?
e.Pourquoi cette erreur est-elle difficile à détecter par un test ?
›Voir le corrigéMasquer le corrigé
a. Oui, si les deux sommets sont dans la même composante connexe. Le DFS visite tous les sommets atteignables.
b. Non, sauf par chance. Le DFS s'engage dans la première direction disponible et peut faire un immense détour avant d'atteindre un sommet pourtant voisin du départ.
c. Parce qu'il explore couche par couche : tous les sommets à une arête, puis à deux, et ainsi de suite. Le premier moment où il atteint un sommet correspond donc nécessairement au plus petit nombre d'arêtes.
d. Remplacer la pile par une file. Le reste de l'algorithme est identique — c'est la seule différence entre les deux parcours.
e. Parce que sur un petit graphe, ou sur un graphe où l'ordre des voisins est favorable, le DFS peut renvoyer le bon résultat. Le test passe, et l'erreur n'apparaît que sur certaines topologies.
3
Un réseau social compte 1 000 000 de comptes, chacun ayant en moyenne 200 relations. Raisonner sur la représentation.
Raisonner
a.Combien de cases occuperait une matrice d'adjacence ? On raisonne en ordre de grandeur.
b.Combien d'arêtes le graphe compte-t-il environ ?
c.Ce graphe est-il dense ou creux ?
d.Quelle représentation choisir, et pourquoi ?
›Voir le corrigéMasquer le corrigé
a. Une matrice compte n² cases :1000000×1000000=1000000000000
Soit mille milliards de cases — hors de portée.
b. Chaque compte a 200 relations, et chaque arête est comptée deux fois :1000000×200÷2=100000000
Soit cent millions d'arêtes.
c. Extrêmement creux : cent millions d'arêtes pour mille milliards de cases possibles, soit un dix-millième.1000000000000÷100000000=10000
d. La liste d'adjacence : son espace est proportionnel au nombre d'arêtes, donc de l'ordre de cent millions et non de mille milliards. Une matrice stockerait presque uniquement des zéros.
4
Parcours et conditions. Raisonner.
Appliquer
a.Que se passe-t-il si l'on oublie de marquer les sommets visités ?
b.Comment reconstituer le chemin trouvé, et non seulement sa longueur ?
c.Pourquoi Dijkstra est-il une généralisation du BFS ?
d.Pourquoi Dijkstra échoue-t-il avec des poids négatifs ?
›Voir le corrigéMasquer le corrigé
a. Un cycle provoque une boucle infinie : l'algorithme revient indéfiniment sur des sommets déjà traités.
b. En mémorisant le prédécesseur de chaque sommet au moment où on l'atteint, puis en remontant depuis l'arrivée jusqu'au départ.
c. Parce que si toutes les arêtes valent 1, les deux algorithmes traitent les sommets dans le même ordre : le sommet non traité le plus proche est alors le suivant dans la file.
d. Parce qu'il fige la distance d'un sommet dès qu'il le traite, en supposant qu'aucun chemin ultérieur ne fera mieux. Un poids négatif rend cette hypothèse fausse, et le résultat est erroné sans être signalé.
Ce qui rapporte des points, ce qui en coûte
Choisir la représentation selon la densité4 ptsPerdu si : Employer une matrice sur un graphe creux
Associer BFS à la file et DFS à la pile4 ptsPerdu si : Inverser les deux structures
Réserver le plus court chemin au BFS5 ptsPerdu si : Employer un DFS pour une distance
Marquer les sommets visités3 ptsPerdu si : Boucler sur un cycle
Énoncer la condition de Dijkstra4 ptsPerdu si : L'appliquer à des poids négatifs
4
La méthode
Programmer un parcours de graphe
1
Choisir la représentation du graphe selon sa densité : matrice ou listes d'adjacence.
2
Créer la structure d'attente adaptée au parcours voulu, file ou pile.
3
Maintenir l'ensemble des sommets déjà visités pour ne jamais traiter un sommet deux fois.
Sans cet ensemble, un cycle fait tourner le parcours indéfiniment.
4
Enregistrer le prédécesseur de chaque sommet atteint afin de pouvoir reconstruire le chemin.
5
Adapter l'algorithme aux poids des arêtes lorsque le coût n'est plus le nombre d'arêtes.
5
Se tester
Touches 1 à 4
NSITerminale
Question 1
Pour organiser un tournoi de tennis, Clara doit vérifier si son graphe de matchs est connexe. Son graphe non-orienté a 8 sommets et la matrice d'adjacence suivante : M=0101000010100000010000001000100000010100000010100000010100000010Combien de composantes connexes contient ce graphe ?
Aucun compte requis — réponds, la correction s'affiche aussitôt.
Graphes — Structures et algorithmes de parcours : c'est en quelle classe ?+
Ce chapitre est au programme de NSI au lycée, en classe de Terminale, année du Baccalauréat. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.
Que faut-il savoir sur Graphes — Structures et algorithmes de parcours ?+
Graphe non-orienté et orienté. Matrice d'adjacence et liste d'adjacence. Parcours : BFS (file) et DFS (pile/récursion). Algorithme de Dijkstra : plus court chemin pondéré. Cycles et connexité. Les notions à maîtriser sont : graphe, BFS, DFS, Dijkstra, matrice d'adjacence, parcours.
Où télécharger la fiche PDF de Graphes — Structures et algorithmes de parcours ?+
Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 6 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.
Le corrigé de Graphes — Structures et algorithmes de parcours est-il fourni ?+
Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.
Graphes — Structures et algorithmes de parcours peut-il tomber au Baccalauréat ?+
Ce chapitre fait partie du programme officiel de Terminale, il entre donc dans le périmètre du Baccalauréat. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.
Comment réviser Graphes — Structures et algorithmes de parcours efficacement ?+
Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.
Faut-il un compte pour s'entraîner sur Graphes — Structures et algorithmes de parcours ?+
Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.
Notions voisines
Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.