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

Parcours de graphes en largeur et en profondeur : fiche de Tle NSI

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

L'essentiel

Un parcours de graphe visite les sommets accessibles depuis un sommet de départ, en marquant les sommets déjà vus.
Le parcours en largeur (BFS) explore la source, puis ses voisins, puis les voisins des voisins : il utilise une file ⁴.
Le parcours en profondeur (DFS) suit un chemin jusqu'au cul-de-sac puis revient en arrière : il utilise une pile ou la récursivité ⁴⁵.
Le BFS donne les distances depuis la source ; le DFS sert surtout à savoir si un chemin existe ⁴⁵.
Les deux servent à calculer les composantes connexes d'un graphe non orienté ⁴⁵.

L'idée d'un parcours de graphe

Le parcours en largeur (BFS)

ExempleCode Python

from collections import deque

def bfs(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

Le parcours en profondeur (DFS)

MéthodeVersion récursive

Le DFS se décrit naturellement de façon récursive : depuis un sommet $s$ , on le marque, puis on s'appelle sur chaque voisin non marqué ⁵.

def dfs(graphe, s, vus=None, ordre=None):
    if vus is None:
        vus, ordre = set(), []
    vus.add(s)
    ordre.append(s)
    for t in graphe[s]:
        if t not in vus:
            dfs(graphe, t, vus, ordre)
    return ordre

Exemple déroulé et comparaison

À retenirTableau de comparaison

	Largeur (BFS)	Profondeur (DFS)
Structure	file	pile ou récursivité
Exploration	couche par couche	chemin jusqu'au bout
Atout	distances, plus courts chemins	existence d'un chemin

La file et la pile sont décrites dans ⁴, la récursivité dans ⁵.

Pièges à éviter

Les questions qu'on se pose

Quand choisir le BFS plutôt que le DFS ?

Choisis le BFS pour trouver des distances ou un plus court chemin dans un graphe non pondéré ⁴. Le DFS convient pour savoir si un chemin existe entre deux sommets ⁵.

Faut-il toujours marquer les sommets visités ?

Oui pour un graphe quelconque, afin de ne pas explorer un sommet plusieurs fois. Dans un arbre, le marquage n'est pas nécessaire ⁴.

Le DFS peut-il s'écrire sans récursivité ?

Oui : on remplace la file du BFS par une pile ⁴. La version récursive reste souvent plus courte à écrire ⁵.

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 en largeur et en profondeur : fiche de Tle NSI

L'essentiel

L'idée d'un parcours de graphe

Le parcours en largeur (BFS)

Le parcours en profondeur (DFS)

Exemple déroulé et comparaison

Pièges à éviter

Questions flash

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur