Numérique et sciences informatiques (spécialité) · TerminaleBac
Parcours de graphes en largeur et en profondeur : quiz de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Le parcours en largeur (BFS) explore d'abord la source, puis ses voisins, puis les voisins des voisins : il utilise une file.4
- Le parcours en profondeur (DFS) suit un chemin jusqu'au cul-de-sac avant de revenir en arrière : il utilise une pile ou la récursivité.45
- Le BFS donne les distances depuis la source dans un graphe non pondéré ; le DFS donne les sommets accessibles depuis un sommet.45
- Dans un graphe avec cycles, il faut marquer les sommets visités pour ne pas les explorer deux fois.4
Avant de commencer
Ce quiz porte sur les deux grands parcours de graphes du programme de NSI : le parcours en largeur et le parcours en profondeur. Tu y croiseras des questions de cours (structure de données utilisée, rôle du marquage, applications) et des questions de simulation sur de petits graphes que tu peux dessiner sur ton brouillon.
Graphe 1 (utilisé dans plusieurs questions) : les arêtes sont A-B, A-C, B-D, B-E et C-F.
Graphe 2 : les arêtes sont A-B, A-C, B-D, C-D et D-E. Il contient un cycle A-B-D-C-A.
Quiz
15 questions · correction immédiate · ton score reste sur ton appareil.
-
Le parcours en largeur retire le sommet placé en tête de la file et range à la fin ses voisins qui n'ont pas encore été explorés.4 Ce fonctionnement « premier entré, premier sorti » explore les sommets par vagues successives. La pile est tentante parce qu'on la connaît bien, mais elle correspond au parcours en profondeur.
-
Si l'on met une pile à la place de la file, l'algorithme de largeur devient un algorithme de profondeur.4 Le marquage reste utile dans un graphe avec cycles et ne change pas le type de parcours. Trier les voisins change seulement l'ordre de visite, pas la stratégie.
-
C'est vrai : les sommets les plus proches de la source sont explorés avant les plus éloignés.4 On explore tous les voisins directs, puis les sommets à distance 2, etc. C'est le parcours en profondeur qui peut s'éloigner très vite de la source.
-
On part de A (file : B, C). On sort B et on ajoute D, E ; on sort C et on ajoute F ; puis D, E, F sortent. L'ordre est A, B, C, D, E, F. La réponse A, B, D, E, C, F est l'ordre d'un parcours en profondeur : c'est l'erreur tentante, car elle explore « à fond » la branche de B avant de passer à C.
-
Depuis A, on va en B (premier voisin), puis en D, cul-de-sac : on revient en B, puis on visite E, cul-de-sac. On revient jusqu'à A, puis C et F.5 L'ordre est A, B, D, E, C, F. L'ordre A, B, C, D, E, F est celui du parcours en largeur.
-
De A on va en B, puis en D. Les voisins de D sont B (déjà visité), C, E : on prend C. C n'a plus de voisin non visité (A et D sont marqués), on revient en D et on visite E. L'ordre est A, B, D, C, E. L'ordre A, B, C, D, E est tentant, mais C n'est pas voisin de B : on ne peut pas passer de B à C directement. Le marquage évite de repartir vers un sommet déjà visité.4
-
Le parcours en largeur permet d'obtenir la distance entre la source et chacun des autres sommets d'un graphe non pondéré.4 Ici, B et C sont à distance 1, D à distance 2 (via B ou C), et E à distance 3 (A-B-D-E). Répondre 2 serait une erreur : E n'est voisin que de D, qui est lui-même à distance 2 de A.
-
À la différence du parcours en largeur, il explore « à fond » chaque chemin : il avance jusqu'à un sommet sans voisin non marqué, puis revient au sommet père.5 Explorer d'abord tous les voisins de la source est la description du parcours en largeur.
-
Le parcours en profondeur permet de savoir s'il existe un chemin entre deux sommets, trouve les sommets accessibles depuis un sommet, et sert au calcul des composantes connexes d'un graphe non orienté.5 Les plus courts chemins relèvent du parcours en largeur, qui explore par distance croissante.4 Sur le graphe 2, le DFS atteint E après A, B, D, C, mais cet ordre ne reflète pas les distances.
-
C'est faux : le parcours en largeur s'applique à un graphe non pondéré, orienté ou non orienté.4 Dans un graphe orienté, on suit simplement les arcs dans leur sens. L'erreur vient de l'exemple de la connexité, qui est précisé pour les graphes non orientés.
-
L'ordre de sortie est A, B, C, D, E, F, donc A, B et C sortent avant D : 3 sommets. Répondre 2 reviendrait à penser que D suit directement son père B, ce qui serait vrai en profondeur (A, B, D) mais pas en largeur : C, voisin de A, est exploré avant D.4
Les questions qu'on se pose
Comment savoir s'il faut choisir un parcours en largeur ou en profondeur ?
Cela dépend de la question posée. Pour des distances ou des plus courts chemins dans un graphe non pondéré, le parcours en largeur convient, car il explore par distance croissante depuis la source.4 Pour savoir s'il existe un chemin, trouver les sommets accessibles ou calculer des composantes connexes, le parcours en profondeur convient.5
L'ordre de visite d'un parcours est-il unique ?
Non. L'ordre dépend du choix des voisins à chaque sommet : alphabétique, selon la liste d'adjacence, etc. Au bac, l'énoncé précise cet ordre ; si ce n'est pas le cas, indique celui que tu prends. Ce qui ne change pas, c'est la stratégie : file pour la largeur, pile ou récursivité pour la profondeur.45
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.