Numérique et sciences informatiques (spécialité) · TerminaleBac

Parcours de graphes (largeur, profondeur) : cours de NSI Terminale

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

Un parcours visite les sommets d'un graphe à partir d'une source, chacun une seule fois grâce au marquage des sommets déjà vus.⁴
Le parcours en largeur (BFS) utilise une file : il explore la source, puis ses voisins, puis les voisins de ses voisins.⁴
Le parcours en profondeur (DFS) s'enfonce dans un chemin jusqu'à un cul-de-sac, puis revient en arrière ; il s'écrit naturellement en récursif, ou avec une pile.⁵⁴
Le BFS donne les distances depuis la source dans un graphe non pondéré ; les deux parcours donnent les sommets accessibles et les composantes connexes.⁴⁵
Pour choisir : plus court chemin en nombre d'arêtes, c'est le BFS ; exploration exhaustive d'un chemin, c'est le DFS.

Pourquoi parcourir un graphe ?

Tu as déjà travaillé sur les arbres binaires : à partir de la racine, tu sais visiter tous les nœuds, en passant par les sous-arbres gauche et droit. Un graphe généralise cette situation. Il n'y a plus de racine imposée, un sommet peut être relié à plusieurs autres, et on peut revenir par un autre chemin sur un sommet déjà rencontré.

On veut pourtant répondre à des questions très concrètes : est-ce que je peux aller du sommet A au sommet G ? Combien d'arêtes faut-il traverser au minimum ? Le réseau est-il en un seul morceau ? Pour y répondre, il faut un procédé systématique qui visite les sommets sans en oublier et sans tourner en rond. C'est le rôle des algorithmes de parcours.

Deux parcours sont au programme de la spécialité NSI : le parcours en largeur et le parcours en profondeur.¹² Dans ce cours, tu vas :

comprendre l'idée de chacun, avec des schémas de déroulement pas à pas ;
les écrire en Python, avec le bon outil (file, pile ou récursivité) ;
savoir lequel choisir selon la question posée, et les utiliser pour calculer des distances et des composantes connexes.

Rappels : graphe, voisins, chemins et représentation en Python

MéthodeReprésenter un graphe en Python

Pour programmer un parcours, le plus pratique est un dictionnaire d'adjacence : chaque clé est un sommet, chaque valeur est la liste de ses voisins. Voici le graphe non orienté qui nous servira d'exemple fil rouge, avec des voisins rangés dans l'ordre alphabétique.

graphe = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E', 'G'],
    'G': ['F'],
}

Puisque le graphe est non orienté, si 'B' figure dans la liste de 'A', alors 'A' figure dans celle de 'B'. Pour connaître les voisins de 'F', il suffit d'écrire graphe['F'], qui vaut ['C', 'E', 'G'].

Le parcours en largeur (BFS)

Le fonctionnement repose sur une file : on sort le sommet qui est en tête, puis on range tout au bout de la file ceux de ses voisins qui n'ont pas encore été vus.⁴ Comme une file ressort les éléments dans l'ordre où ils sont arrivés (premier entré, premier sorti), les sommets découverts les premiers sont aussi traités les premiers. C'est ce qui garantit l'exploration « couche par couche ».

Pour ne jamais explorer deux fois le même sommet, on marque les sommets déjà visités.⁴ Sans ce marquage, un graphe qui contient un cycle ferait tourner l'algorithme indéfiniment : on repasserait sans cesse par les mêmes sommets. Dans un arbre, aucun cycle n'existe et le marquage devient inutile.⁴

InitialiserMettre la source dans la file et la marquer.
DéfilerRetirer le sommet en tête de file.
AjouterMarquer ses voisins et les ajouter en fin de file.
RépéterRecommencer tant que la file n'est pas vide.

Les étapes du parcours en largeur · Marquer à l'ajout dans la file évite les doublons.

Trace du parcours en largeur depuis A
Sommet défilé	File ensuite	Sommets marqués
A	B, C	A, B, C
B	C, D, E	A, B, C, D, E
C	D, E, F	A, B, C, D, E, F
D	E, F	A, B, C, D, E, F
E	F	A, B, C, D, E, F
F	G	A, B, C, D, E, F, G
G	vide	A, B, C, D, E, F, G

Trace du parcours en largeur depuis A · Chaque ligne traite un seul sommet.

MéthodeLe parcours en largeur en Python

from collections import deque

def parcours_largeur(graphe, source):
    vus = {source}
    file = deque([source])
    ordre = []
    while file:
        s = file.popleft()
        ordre.append(s)
        for t in graphe[s]:
            if t not in vus:
                vus.add(t)
                file.append(t)
    return ordre

L'appel parcours_largeur(graphe, 'A') renvoie ['A', 'B', 'C', 'D', 'E', 'F', 'G']. L'ensemble vus joue le rôle du marquage ; la file deque permet de retirer en tête (popleft) et d'ajouter en fin (append) efficacement. Si ton cours utilise une classe File avec enfiler et defiler, le raisonnement est strictement le même.

Le parcours en largeur calcule des distances

Pourquoi cette propriété est-elle vraie ? Voici l'idée, qui est un raisonnement et non une démonstration complète. Au départ, la file contient seulement la source, à distance 0. Quand on la retire, on ajoute ses voisins, tous à distance 1. Quand on retire ensuite ces sommets à distance 1, on ajoute leurs voisins non marqués, qui sont à distance 2, et ils se placent derrière tous ceux de distance 1 déjà présents. Comme la file est respectée, on ne traite jamais un sommet à distance $d+1$ avant d'avoir traité tous les sommets à distance $d$ .

Pour exploiter cette propriété, il suffit de noter, pour chaque sommet découvert, la distance de son prédécesseur augmentée de 1.

MéthodeCalculer les distances depuis une source

from collections import deque

def distances(graphe, source):
    dist = {source: 0}
    file = deque([source])
    while file:
        s = file.popleft()
        for t in graphe[s]:
            if t not in dist:
                dist[t] = dist[s] + 1
                file.append(t)
    return dist

Ici le dictionnaire dist remplace l'ensemble vus : un sommet est marqué dès qu'il possède une distance. Sur le graphe fil rouge, distances(graphe, 'A') renvoie {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2, 'G': 3}.

ExempleRetrouver un plus court chemin

Pour obtenir non seulement la distance mais le chemin lui-même, on mémorise pour chaque sommet son prédécesseur (le sommet qui l'a fait découvrir) :

def plus_court_chemin(graphe, source, but):
    pred = {source: None}
    file = deque([source])
    while file:
        s = file.popleft()
        for t in graphe[s]:
            if t not in pred:
                pred[t] = s
                file.append(t)
    if but not in pred:
        return None
    chemin = []
    s = but
    while s is not None:
        chemin.append(s)
        s = pred[s]
    return chemin[::-1]

Sur le graphe fil rouge, G a été découvert par F, F par C, et C par A. En remontant puis en inversant, on obtient le chemin ['A', 'C', 'F', 'G'], de longueur 3. Si but n'est pas accessible, la fonction renvoie None.

Le parcours en profondeur (DFS)

Le principe est celui d'un promeneur têtu : depuis un sommet, il choisit un voisin et avance, puis choisit un voisin du voisin, et ainsi de suite. Il suit ainsi un chemin jusqu'à une impasse ou jusqu'à rencontrer un sommet déjà vu. Il remonte alors jusqu'au dernier sommet qui offrait une autre direction, et part explorer celle-ci. Le parcours prend fin quand tous les sommets atteignables depuis la source ont été vus.⁵

Le nom vient de cette manière d'aller « à fond » dans chaque chemin avant d'en essayer un autre, à l'inverse du parcours en largeur.⁵ Pour chaque sommet, on le marque, puis on prend le premier voisin non marqué, et ainsi de suite jusqu'à un sommet sans voisin à visiter ; on revient alors au sommet précédent.⁵

MéthodeLe parcours en profondeur en Python (version récursive)

L'exploration depuis un sommet s s'appelle elle-même pour chaque voisin non encore visité.⁵

def explorer(graphe, s, vus, ordre):
    vus.add(s)
    ordre.append(s)
    for t in graphe[s]:
        if t not in vus:
            explorer(graphe, t, vus, ordre)

def parcours_profondeur(graphe, source):
    vus = set()
    ordre = []
    explorer(graphe, source, vus, ordre)
    return ordre

Le « retour en arrière » n'est pas écrit explicitement : il se produit tout seul quand un appel récursif se termine et que l'exécution reprend dans l'appel précédent, au voisin suivant de la boucle for.

ExempleDéroulement sur le graphe fil rouge, depuis A

On visite A. Son premier voisin non visité est B : on visite B.
Depuis B, A est déjà vu ; le premier voisin non visité est D : on visite D.
D n'a pour voisin que B, déjà vu : cul-de-sac. On revient à B.
Depuis B, le voisin suivant est E : on visite E.
Depuis E, B est vu ; le voisin F est nouveau : on visite F.
Depuis F, le premier voisin non visité est C : on visite C. Les voisins de C, A et F, sont déjà vus. On revient à F.
Depuis F, E est vu ; le voisin G est nouveau : on visite G. Cul-de-sac.
On remonte jusqu'à A : plus aucun voisin à explorer. Fin.

L'ordre de visite est A, B, D, E, F, C, G. Compare avec le parcours en largeur (A, B, C, D, E, F, G) : C, voisin direct de A, est visité en dernier avant G, parce que le parcours s'est d'abord enfoncé dans la branche de B.

MéthodeVersion itérative avec une pile

Si l'on remplace la file par une pile dans l'algorithme du parcours en largeur, on obtient un parcours en profondeur.⁴ Une pile ressort en premier le dernier élément ajouté (dernier entré, premier sorti), donc on s'occupe toujours du sommet découvert le plus récemment, ce qui oblige à s'enfoncer.

def parcours_profondeur_pile(graphe, source):
    vus = set()
    pile = [source]
    ordre = []
    while pile:
        s = pile.pop()
        if s in vus:
            continue
        vus.add(s)
        ordre.append(s)
        for t in reversed(graphe[s]):
            if t not in vus:
                pile.append(t)
    return ordre

On empile les voisins en ordre inverse pour que le premier voisin soit dépilé en premier, comme dans la version récursive. Sur le graphe fil rouge, on retrouve ['A', 'B', 'D', 'E', 'F', 'C', 'G']. Ici le marquage se fait au dépilage, car un sommet peut être empilé plusieurs fois avant d'être traité.

Comparer, choisir, utiliser

Largeur et profondeur côte à côte
Critère	Largeur (BFS)	Profondeur (DFS)
Structure	File	Pile ou récursivité
Exploration	Par couches autour de la source	Un chemin jusqu'au cul-de-sac, puis retour
Ordre sur le graphe fil rouge	A, B, C, D, E, F, G	A, B, D, E, F, C, G
Usage typique	Distances, plus courts chemins	Existence de chemin, labyrinthe

Largeur et profondeur côte à côte · Les deux parcours visitent les mêmes sommets accessibles, dans un ordre différent.

Le parcours en largeur découvre le graphe par couches successives ; le parcours en profondeur le découvre en suivant un chemin le plus loin possible. Les deux visitent exactement les mêmes sommets : ceux qui sont accessibles depuis la source. Pour le parcours en profondeur, ces sommets sont précisément ceux que l'algorithme a marqués, qu'il s'agisse d'un graphe orienté ou non orienté.⁵ Le parcours en largeur atteint lui aussi tous les sommets accessibles depuis la source.⁴

Sur un graphe non orienté, la propriété d'accessibilité sert à calculer les composantes connexes.⁵ Le parcours en largeur permet aussi de tester si un tel graphe est connexe et d'en obtenir les composantes connexes, avec un coût linéaire par rapport à la taille du graphe.⁴

La méthode est la suivante. On part d'un sommet quelconque et on lance un parcours : tous les sommets marqués forment une première composante. S'il reste des sommets non marqués, on en choisit un et on relance un parcours depuis lui, en gardant les marques précédentes : on obtient la deuxième composante, et ainsi de suite. Le graphe est connexe si un seul parcours depuis un sommet quelconque a marqué tous les sommets.

MéthodeCompter les composantes connexes

def nb_composantes(graphe):
    vus = set()
    nb = 0
    for s in graphe:
        if s not in vus:
            nb += 1
            explorer(graphe, s, vus, [])
    return nb

On réutilise la fonction explorer du parcours en profondeur. À chaque fois que la boucle rencontre un sommet non encore vu, c'est qu'on entre dans une nouvelle composante : on incrémente le compteur, puis l'exploration marque toute la composante. L'ensemble vus est partagé entre tous les appels, c'est ce qui évite de compter deux fois une même composante.

Réussir les questions de parcours au bac

Exercices corrigés

Exercice 1 Dérouler les deux parcours à la main

★☆☆Environ 10 min

On considère le graphe non orienté suivant, donné par ses listes de voisins rangés dans l'ordre alphabétique (le sommet S est la source) :

S : A, B
A : C, S
B : C, D, S
C : A, B, E
D : B
E : C

Donne l'ordre de visite d'un parcours en largeur depuis S.
Donne l'ordre de visite d'un parcours en profondeur depuis S.
Quelle est la distance de S à E ?

Indice 1

Pour la largeur, tiens à jour le contenu de la file après chaque sommet retiré.

Indice 2

Pour la profondeur, avance toujours vers le premier voisin non visité dans l'ordre alphabétique, et reviens en arrière seulement en cas de cul-de-sac.

Voir la correction pas à pas

Largeur : la file contient S. On retire S et on ajoute A et B : file A, B.
On retire A : son voisin C est nouveau, file B, C. On retire B : C est déjà marqué, D est nouveau, file C, D.
On retire C : E est nouveau, file D, E. On retire D, puis E. Ordre en largeur : S, A, B, C, D, E.
Profondeur : on visite S, puis son premier voisin A, puis le premier voisin non visité de A, c'est-à-dire C.
Depuis C, A est vu et B est nouveau : on visite B. Depuis B, C et S sont vus, D est nouveau : on visite D, cul-de-sac, retour à B, puis à C.
Depuis C, le voisin E est nouveau : on le visite. Ordre en profondeur : S, A, C, B, D, E.
Distance de S à E : E est découvert via C, lui-même découvert via A, découvert depuis S. Le chemin S, A, C, E compte 4 sommets donc 3 arêtes, et aucun chemin plus court n'existe puisque E n'est voisin que de C, qui est à distance 2.

Les deux ordres diffèrent dès le troisième sommet : en largeur, B (voisin de S) passe avant C ; en profondeur, C est atteint par A avant que B soit visité. La distance, elle, se lit sur le parcours en largeur : E est découvert au troisième « cercle » autour de S.

Exercice 2 Compter les composantes connexes

★★☆Environ 10 min

Voici un graphe non orienté, avec les voisins de chaque sommet :

1 : 2, 3
2 : 1, 4
3 : 1, 4
4 : 2, 3, 5
5 : 4
6 : 7
7 : 6

Lance un parcours en profondeur depuis 1. Quels sommets sont marqués à la fin ?
Ce graphe est-il connexe ? Justifie.
Combien de composantes connexes compte-t-il ?

Indice 1

Les sommets marqués à la fin d'un parcours sont exactement ceux accessibles depuis la source.

Indice 2

Relance un parcours depuis un sommet non marqué, en gardant les marques précédentes.

Voir la correction pas à pas

On visite 1, puis 2 (premier voisin), puis 4 (voisin de 2).
Depuis 4, 2 est vu et 3 est nouveau : on visite 3. Les voisins de 3, 1 et 4, sont vus : retour à 4.
Depuis 4, le voisin 5 est nouveau : on le visite. Plus rien à explorer. Les sommets marqués sont 1, 2, 4, 3, 5 (dans cet ordre).
Les sommets 6 et 7 ne sont pas marqués : aucun chemin ne les relie à 1. Le graphe n'est donc pas connexe.
On relance un parcours depuis 6 en gardant les marques : il atteint 7 et s'arrête. Cela donne une deuxième composante, {6, 7}.
Tous les sommets sont désormais marqués : il y a 2 composantes connexes, {1, 2, 3, 4, 5} et {6, 7}.

Chaque nouveau lancement de parcours depuis un sommet non marqué correspond à une nouvelle composante. C'est exactement ce que compte la fonction nb_composantes du cours.

Exercice 3 Écrire une fonction d'accessibilité

★★★Environ 15 min

On représente un graphe par un dictionnaire d'adjacence, comme dans le cours.

Écris une fonction existe_chemin(graphe, depart, arrivee) qui renvoie True s'il existe un chemin de depart à arrivee, et False sinon. Tu peux choisir le parcours de ton choix.
Pourquoi ta fonction se termine-t-elle même si le graphe contient un cycle ?
Sur le graphe de l'exercice 2, que renvoient existe_chemin(g, 3, 5) et existe_chemin(g, 3, 6) ?

Indice 1

Un sommet est accessible depuis depart s'il est marqué à la fin d'un parcours lancé depuis depart.

Indice 2

Tu peux t'arrêter dès que tu rencontres arrivee.

Voir la correction pas à pas

On choisit un parcours en largeur avec une file et un ensemble vus, en partant de depart.
On écrit : def existe_chemin(graphe, depart, arrivee): puis vus = {depart} et file = deque([depart]).
Dans la boucle while file, on retire s en tête ; si s == arrivee, on renvoie True.
Pour chaque voisin t de s non présent dans vus, on l'ajoute à vus et à la file.
Si la boucle se termine sans avoir rencontré arrivee, on renvoie False.
Terminaison : chaque sommet entre au plus une fois dans la file grâce à vus, et le graphe a un nombre fini de sommets, donc la file finit par se vider, cycle ou non.
Résultats : existe_chemin(g, 3, 5) renvoie True (3, 4, 5) et existe_chemin(g, 3, 6) renvoie False, car 6 n'est pas dans la composante de 3.

Une fonction d'accessibilité est un parcours dont on interroge le marquage. La preuve de terminaison repose toujours sur le même argument : un ensemble fini de sommets et un marquage qui empêche de les ajouter deux fois.

Les questions qu'on se pose

Faut-il toujours marquer les sommets visités ?

Oui, dès que le graphe peut contenir un cycle. Le marquage évite d'explorer plusieurs fois le même sommet.⁴ Dans un arbre, il n'y a pas de cycle et le marquage n'est pas nécessaire.⁴ Dans le doute, marque : cela ne coûte presque rien et protège d'une boucle infinie.

Quand préférer le parcours en largeur au parcours en profondeur ?

Choisis la largeur quand la question porte sur une distance ou un plus court chemin en nombre d'arêtes, car les sommets y sont explorés par distance croissante à la source.⁴ Choisis la profondeur quand tu veux simplement savoir si un chemin existe ou explorer à fond, notamment en récursif, car son écriture est très naturelle.⁵ Pour l'accessibilité et les composantes connexes, les deux conviennent.

Pourquoi mon parcours en profondeur donne-t-il un ordre différent de celui du corrigé ?

L'ordre de visite dépend de l'ordre dans lequel les voisins sont examinés. Si le corrigé suit l'ordre alphabétique et que tu suis un autre ordre, tu obtiens un parcours valide mais différent. Relis l'énoncé pour repérer la consigne, et vérifie aussi que tu reviens bien au dernier sommet qui offrait encore un chemin, et pas au premier.⁵

Quelle est la différence entre la version récursive et la version avec pile du parcours en profondeur ?

Elles visitent les sommets dans le même ordre si tu empiles les voisins en ordre inverse. La version récursive laisse Python gérer la pile des appels ; la version itérative gère la pile à la main. Le parcours en profondeur se décrit naturellement de manière récursive,⁵ mais l'itératif évite l'erreur de dépassement de profondeur sur de très grands graphes.

Qu'est-ce qui tombe au bac sur ce chapitre ?

On te demande surtout de dérouler un parcours à la main sur un petit graphe (ordre de visite, contenu de la file ou de la pile), de compléter ou de corriger un programme Python, et d'utiliser un parcours pour répondre à une question : un chemin existe-t-il, quelle est la distance, combien de composantes connexes ? Entraîne-toi à faire le tableau « sommet traité, file ou pile, sommets marqués ».

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.

Signaler une erreur sur cette page

Parcours de graphes (largeur, profondeur) : cours de NSI Terminale

L'essentiel

Pourquoi parcourir un graphe ?

Rappels : graphe, voisins, chemins et représentation en Python

Le parcours en largeur (BFS)

Le parcours en largeur calcule des distances

Le parcours en profondeur (DFS)

Comparer, choisir, utiliser

Réussir les questions de parcours au bac

Exercices corrigés

Exercice 1 Dérouler les deux parcours à la main

Exercice 2 Compter les composantes connexes

Exercice 3 Écrire une fonction d'accessibilité

Quiz

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur