Numérique et sciences informatiques (spécialité) · TerminaleBac
Parcours de graphes : exercices corrigés de NSI en Terminale
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Le parcours en largeur (BFS) explore le sommet source, puis ses voisins, puis les voisins des voisins : il utilise une file 4.
- Le parcours en profondeur (DFS) suit un chemin jusqu'à une impasse avant de revenir en arrière : il se décrit naturellement de façon récursive, ou avec une pile 45.
- Le BFS visite les sommets par distance croissante à la source : il donne les plus courts chemins dans un graphe non pondéré 4.
- Dans les deux parcours, un sommet marqué n'est jamais retraité, ce qui évite de tourner en rond 45.
- Ces parcours trouvent tous les sommets accessibles depuis la source, donc les composantes connexes d'un graphe non orienté 45.
Comment utiliser ces exercices
Ces exercices te font dérouler à la main les deux parcours de graphe du programme de spécialité NSI. Les algorithmes sur les arbres binaires, que tu connais déjà, sont le point de départ : un arbre est un cas particulier de graphe. Cherche d'abord seul, ouvre un indice si tu bloques, puis compare ta démarche à la correction étape par étape. Dans chaque exercice, on traite les voisins dans l'ordre alphabétique (ou croissant pour des nombres). Sans cette convention, plusieurs ordres de visite seraient possibles et ta réponse ne pourrait pas être comparée à la correction.
Les exercices
Exercice 1 Ordre de visite en largeur
Voici un graphe non orienté, donné par ses listes de voisins.
| Sommet | Voisins |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E, F |
| D | B, G |
| E | C |
| F | C, G |
| G | D, F |
Donne l'ordre dans lequel un parcours en largeur partant de A visite les sommets, en traitant les voisins dans l'ordre alphabétique.
Indice 1
Écris le contenu de la file après chaque sommet traité.
Indice 2
Un voisin déjà dans la file ou déjà visité n'est pas ajouté une seconde fois.
Voir la correction pas à pas
On part de la file [A] et on marque A. On retire A : ordre = A. Ses voisins B et C sont ajoutés, file = [B, C].
On retire B : ordre = A, B. Ses voisins sont A (marqué) et D (nouveau). File = [C, D].
On retire C : ordre = A, B, C. Ses voisins sont A (marqué), E et F (nouveaux). File = [D, E, F].
On retire D : ordre = A, B, C, D. Ses voisins sont B (marqué) et G (nouveau). File = [E, F, G].
On retire E, puis F, puis G. Pour F, le voisin G est déjà dans la file : on ne l'ajoute pas. Pour G, tous les voisins sont marqués.
L'ordre de visite est A, B, C, D, E, F, G. Les sommets sont bien visités par distance croissante à la source : A d'abord, puis B et C, puis D, E et F, enfin G 4.
Exercice 2 Ordre de visite en profondeur
On reprend le graphe de l'exercice précédent.
| Sommet | Voisins |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E, F |
| D | B, G |
| E | C |
| F | C, G |
| G | D, F |
Donne l'ordre de visite d'un parcours en profondeur récursif partant de A, en traitant les voisins dans l'ordre alphabétique.
Indice 1
Après chaque visite, prends le premier voisin non marqué, sans repasser par la source.
Indice 2
Quand un sommet n'a plus de voisin non marqué, remonte au sommet qui l'a appelé.
Voir la correction pas à pas
On visite A. Son premier voisin non marqué est B : on descend vers B.
On visite B. Le voisin A est marqué, D ne l'est pas : on descend vers D.
On visite D. Le voisin B est marqué, G ne l'est pas : on descend vers G.
On visite G. Le voisin D est marqué, F ne l'est pas : on descend vers F.
On visite F. Le voisin C n'est pas marqué : on descend vers C. On visite C : A est marqué, E ne l'est pas, on descend vers E.
On visite E : son seul voisin C est marqué, c'est une impasse. On remonte jusqu'à A : plus aucun voisin non marqué nulle part, le parcours est terminé.
L'ordre est A, B, D, G, F, C, E. Compare avec l'ordre en largeur A, B, C, D, E, F, G : le parcours en profondeur s'enfonce dans un chemin avant d'explorer les autres voisins de A 5.
Exercice 3 Suivre la taille de la file
On exécute le parcours en largeur de l'exercice 1 sur le même graphe, depuis A. On note la taille de la file juste après avoir ajouté les voisins non marqués du sommet qui vient d'être retiré. Quelle est la plus grande taille atteinte ?
| Sommet | Voisins |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E, F |
| D | B, G |
| E | C |
| F | C, G |
| G | D, F |
Indice 1
Dresse un tableau : sommet retiré, contenu de la file, taille.
Indice 2
Ne compte pas le sommet qui vient d'être retiré.
Voir la correction pas à pas
Retrait de A : file = [B, C], taille 2.
Retrait de B : file = [C, D], taille 2.
Retrait de C : file = [D, E, F], taille 3.
Retrait de D : file = [E, F, G], taille 3.
Retrait de E : file = [F, G], taille 2. Retrait de F : file = [G], taille 1. Retrait de G : file = [], taille 0.
La plus grande valeur du tableau est 3.
La file contient au plus 3 sommets. Elle contient à chaque instant les sommets repérés mais pas encore traités : c'est la « frontière » de l'exploration, qui avance couche par couche 4.
Exercice 4 Largeur ou profondeur ?
Pour chaque problème, indique quel parcours est le mieux adapté, ou si les deux conviennent, et justifie en une phrase.
- Trouver un chemin comportant le moins d'arêtes possible entre deux sommets d'un graphe non pondéré.
- Savoir s'il existe un chemin d'un sommet à un autre.
- Calculer les composantes connexes d'un graphe non orienté.
Indice 1
Rappelle-toi dans quel ordre le parcours en largeur découvre les sommets.
Indice 2
Pour la question 3, demande-toi ce que les deux parcours ont en commun.
Voir la correction pas à pas
Question 1 : le parcours en largeur visite les sommets par distance croissante au sommet source, ce qui permet de calculer des plus courts chemins vers tous les sommets 4. C'est donc le BFS.
Question 2 : tester l'existence d'un chemin entre deux sommets est l'usage le plus simple du parcours en profondeur 5. Le BFS convient aussi, mais le DFS suffit.
Question 3 : les deux parcours trouvent tous les sommets accessibles depuis la source, donc la composante de celle-ci dans un graphe non orienté 45. Les deux conviennent.
Retiens la règle : distance minimale en nombre d'arêtes → largeur ; simple accessibilité ou connexité → l'un ou l'autre, la profondeur étant souvent plus facile à écrire récursivement 5.
Exercice 5 Le chemin du DFS est-il le plus court ?
Sur le graphe ci-dessous, on cherche à atteindre F depuis A.
| Sommet | Voisins |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E, F |
| D | B, G |
| E | C |
| F | C, G |
| G | D, F |
- Donne la longueur (en arêtes) du chemin de A à F construit par le parcours en profondeur de l'exercice 2, en suivant qui a découvert qui.
- Donne la distance de A à F obtenue par un parcours en largeur.
- Calcule l'écart entre les deux longueurs.
Indice 1
Dans le DFS, chaque sommet est découvert depuis le sommet qui l'a appelé : remonte de F vers A.
Indice 2
Dans le BFS, la distance d'un sommet est le numéro de la couche où on le découvre.
Voir la correction pas à pas
Dans le DFS : F est découvert depuis G, G depuis D, D depuis B, B depuis A. Le chemin est A, B, D, G, F, soit 4 arêtes.
Dans le BFS : A est à la distance 0, C est découvert depuis A (distance 1), F est découvert depuis C (distance 2). Le chemin A, C, F compte 2 arêtes.
L'écart est 4 − 2 = 2 arêtes.
Le chemin du DFS compte 2 arêtes de plus que le chemin le plus court. Le parcours en profondeur trouve un chemin, mais pas forcément le plus court ; c'est le parcours en largeur qui garantit des plus courts chemins dans un graphe non pondéré 4.
Exercice 6 Compter les composantes connexes
Un graphe non orienté a pour sommets 1 à 8 et pour arêtes : 1-2, 2-3, 1-3, 4-5, 5-6, 7-8.
On lance un parcours (largeur ou profondeur) depuis le plus petit sommet non marqué, jusqu'à ce que tous les sommets soient marqués. Combien de lancements faut-il ?
Indice 1
Un lancement marque exactement les sommets accessibles depuis sa source.
Indice 2
Dessine le graphe : certains groupes de sommets ne sont reliés à aucun autre.
Voir la correction pas à pas
Premier lancement depuis 1 : sont marqués 1, 2 et 3, qui sont accessibles les uns depuis les autres.
Le plus petit sommet non marqué est 4. Deuxième lancement : sont marqués 4, 5 et 6.
Le plus petit sommet non marqué est 7. Troisième lancement : sont marqués 7 et 8.
Tous les sommets sont marqués : on s'arrête après 3 lancements.
Exercice 7 Lire un code de parcours en largeur
Voici une fonction Python où g est un dictionnaire de listes de voisins.
def largeur(g, s):
vus = {s}
file = [s]
ordre = []
while file:
x = file.pop(0)
ordre.append(x)
for y in g[x]:
if y not in vus:
vus.add(y)
file.append(y)
return ordre
On l'appelle sur le graphe suivant, avec s = 'A'.
| Sommet | Voisins |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E, F |
| D | B, G |
| E | C |
| F | C, G |
| G | D, F |
Combien de fois le test y not in vus est-il évalué pendant l'exécution ?
Indice 1
Le test est évalué une fois par voisin de chaque sommet retiré de la file.
Indice 2
Chaque sommet est retiré une seule fois : additionne le nombre de voisins de chaque sommet.
Voir la correction pas à pas
Chaque sommet est retiré de la file exactement une fois, car il n'y est ajouté qu'une fois grâce au marquage
vus.À chaque retrait, la boucle
forexamine tous les voisins du sommet : le test est évalué autant de fois que le sommet a de voisins.Nombres de voisins : A 2, B 2, C 3, D 2, E 1, F 2, G 2.
Total : 2 + 2 + 3 + 2 + 1 + 2 + 2 = 14.
Le test est évalué 14 fois, soit deux fois le nombre d'arêtes (7), car chaque arête est regardée depuis ses deux extrémités. Le travail est proportionnel à la taille du graphe, ce qui correspond à la complexité linéaire du parcours en largeur 4.
Exercice 8 Sommets accessibles dans un graphe orienté
Un graphe orienté a pour sommets 1 à 6 et pour arcs : 1→2, 1→3, 2→4, 3→4, 4→5, 5→2, 6→1.
- Donne l'ordre de visite d'un parcours en profondeur récursif depuis 1, en traitant les voisins dans l'ordre croissant.
- Combien de sommets sont marqués à la fin du parcours ?
- Pourquoi le marquage est-il indispensable ici ?
Indice 1
Un arc ne se parcourt que dans son sens : le sommet 6 mène à 1, mais pas l'inverse.
Indice 2
Repère le cycle 2→4→5→2.
Voir la correction pas à pas
On visite 1. Ses successeurs sont 2 et 3 : on commence par 2.
On visite 2, puis son successeur 4, puis son successeur 5. Le successeur de 5 est 2, déjà marqué : impasse, on remonte jusqu'à 1.
Le successeur 3 de 1 n'est pas marqué : on le visite. Son successeur 4 est déjà marqué. Ordre : 1, 2, 4, 5, 3.
Les sommets marqués sont 1, 2, 3, 4 et 5, soit 5 sommets. Le sommet 6 n'est pas accessible depuis 1, car l'arc 6→1 va dans l'autre sens.
Sans marquage, on bouclerait indéfiniment sur le cycle 2→4→5→2.
Exercice 9 Sortir d'un labyrinthe
Un labyrinthe est une grille de 3 lignes et 4 colonnes. Les cases # sont des murs, les autres sont libres. On se déplace d'une case à une case voisine (haut, bas, gauche, droite), sans traverser un mur. Les cases sont repérées par (ligne ; colonne), en partant de (0 ; 0) en haut à gauche.
| col. 0 | col. 1 | col. 2 | col. 3 | |
|---|---|---|---|---|
| ligne 0 | départ | libre | # | arrivée |
| ligne 1 | libre | # | libre | libre |
| ligne 2 | libre | libre | libre | libre |
Le graphe a pour sommets les cases libres, avec une arête entre deux cases libres voisines. Quel est le nombre minimal de déplacements pour aller du départ (0 ; 0) à l'arrivée (0 ; 3) ?
Indice 1
Fais un parcours en largeur depuis (0 ; 0) en notant la distance de chaque case découverte.
Indice 2
Le voisin (0 ; 1) du départ est une impasse : les cases (0 ; 2) et (1 ; 1) sont des murs.
Voir la correction pas à pas
Distance 0 : (0 ; 0). Ses voisins libres sont (0 ; 1) et (1 ; 0), à la distance 1.
(0 ; 1) n'a aucun voisin libre non marqué (ses voisins sont des murs) : c'est une impasse. (1 ; 0) mène à (2 ; 0), à la distance 2.
(2 ; 0) mène à (2 ; 1), distance 3. Puis (2 ; 1) mène à (2 ; 2), distance 4.
(2 ; 2) mène à (1 ; 2) et (2 ; 3), à la distance 5. Puis (1 ; 2) et (2 ; 3) mènent à (1 ; 3), distance 6.
(1 ; 3) mène à (0 ; 3), distance 7. C'est la case d'arrivée.
Il faut au minimum 7 déplacements. Comme le parcours en largeur explore les sommets par distance croissante au départ, la première fois qu'il atteint l'arrivée, la distance trouvée est minimale 4. Un parcours en profondeur, lui, explorerait « à fond » une branche, comme on le fait pour chercher la sortie d'un labyrinthe sans tourner en rond 5, mais il ne garantirait pas ce minimum.
Les questions qu'on se pose
Comment savoir dans quel ordre traiter les voisins à l'examen ?
Le sujet le précise presque toujours (ordre alphabétique, ordre des listes d'adjacence, ordre croissant). Si rien n'est dit, indique ta convention en début de réponse. Le résultat d'un parcours dépend de cet ordre, mais la propriété essentielle ne change pas : le parcours en largeur visite les sommets par distance croissante à la source 4.
Quelle est la différence entre une file et une pile dans ces parcours ?
Une file sert le sommet le plus ancien : c'est ce qui donne le parcours en largeur. Une pile sert le sommet le plus récent : c'est ce qui donne le parcours en profondeur 4. Le DFS peut aussi s'écrire sans pile explicite, par récursivité, car les appels récursifs jouent eux-mêmes le rôle de la pile 5.
Sources
Programme visé : Numérique et sciences informatiques - spécialité Terminale - Algorithmique et graphes · Ministère de l'Éducation nationale
- Numérique et sciences informatiques - spécialité Terminale - Algorithmique et graphes, Ministère de l'Éducation nationale. Consulté le 7 novembre 2026.
- Ressources accompagnement NSI - Récursivité et structures de données, Éduscol. Consulté le 7 novembre 2026.
- Algorithmique des graphes - Cours avancé, CNRS - LIRIS. Consulté le 7 novembre 2026.
- Algorithme de parcours en largeur, Wikipédia. Consulté le 7 novembre 2026.
- Algorithme de parcours en profondeur, Wikipédia. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.