Parcours de graphes : BFS et DFS

Vue d'ensemble

Une fois un graphe représenté en machine, la première chose qu'on veut faire est de le parcourir : visiter tous les sommets accessibles depuis un point de départ, sans jamais tourner en rond. Deux stratégies, au programme de première année, se disputent l'ordre de visite : le parcours en largeur (BFS, breadth-first search) qui explore par cercles concentriques, et le parcours en profondeur (DFS, depth-first search) qui plonge aussi loin que possible avant de revenir. Ils partagent le même squelette — marquer les sommets déjà vus pour ne pas boucler — et ne diffèrent que par la structure qui gère les sommets en attente : une file pour BFS, une pile (ou la récursion) pour DFS. Cette fiche code les deux, les décrypte, les trace pas à pas, et montre pourquoi BFS donne « gratuitement » le plus court chemin.

Au programme (tronc commun, 1^re année — BO 2021) — Parcours d'un graphe : parcours en largeur et parcours en profondeur ; utilisation d'une file (largeur) et d'une pile ou de la récursivité (profondeur) ; accessibilité, connexité ; plus court chemin en nombre d'arêtes par parcours en largeur. Le plus court chemin dans un graphe pondéré (Dijkstra) fait l'objet d'une autre fiche.

Prérequis

Représenter un graphe par listes d'adjacence (dictionnaire sommet → voisins) (fiche « graphes »)
Files et piles : deque, append/popleft/pop (fiche « piles et files »)
Récursivité : cas de base, pile d'appels (fiche « récursivité »)

🎯 Accompagnement Majorant

BFS et DFS, c'est le même code à une structure près — mais cette différence change tout. La confondre, ou oublier de marquer les sommets vus, sont les erreurs les plus fréquentes aux concours. Nos mentors alumni X · Centrale · Mines te font tracer les deux parcours à la main jusqu'à ce que le mécanisme devienne limpide.

Trouver un mentor →

1. Le squelette commun : marquer, mettre en réserve, traiter

Parcourir un graphe, c'est visiter les sommets de proche en proche à partir d'un sommet de départ. Deux dangers : revisiter un sommet (et boucler indéfiniment sur un cycle), ou en oublier. La parade est la même pour les deux parcours :

📐 Le principe, en trois ingrédients.

Un ensemble vus des sommets déjà rencontrés, pour ne jamais les traiter deux fois.
Une réserve des sommets rencontrés mais pas encore traités.
Une boucle : tant que la réserve n'est pas vide, on en retire un sommet, on le traite, et on ajoute à la réserve ses voisins encore inconnus (qu'on marque aussitôt vus).

💡 Toute la différence est dans la réserve. Si la réserve est une file (premier entré, premier sorti — FIFO), on obtient le parcours en largeur. Si c'est une pile (dernier entré, premier sorti — LIFO), ou si l'on utilise la récursion, on obtient le parcours en profondeur. Même squelette, ordre de visite radicalement différent.

Pour tout illustrer, on fixe un graphe non orienté à six sommets, donné par ses listes d'adjacence :

from collections import deque

g = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

🔍 Décryptage ligne par ligne

from collections import dequeOn importe la file efficace. deque (« double-ended queue ») permet de retirer en tête avec popleft() en

O (1)

— indispensable pour BFS, là où liste.pop(0) coûterait

O (n)

(voir fiche « piles et files »).

g = { "A": ["B", "C"], ... }Le graphe fil rouge. Depuis A, on atteint B et C ; depuis B, on atteint D et E ; etc. Ce graphe est choisi pour que largeur et profondeur donnent des ordres visiblement différents.

2. Parcours en largeur (BFS) — la file

Le parcours en largeur explore le graphe par cercles concentriques : d'abord le sommet de départ, puis tous ses voisins (distance 1), puis les voisins des voisins (distance 2), etc. La réserve est une file.

def bfs(g, depart):
    vus = {depart}          # sommets deja rencontres
    file = deque([depart])  # reserve : une FILE
    ordre = []
    while file:
        s = file.popleft()  # on retire le PLUS ANCIEN (FIFO)
        ordre.append(s)     # on traite s
        for v in g[s]:
            if v not in vus:
                vus.add(v)      # marque des la rencontre
                file.append(v)  # ajoute en fin de file
    return ordre

print(bfs(g, "A"))   # ['A', 'B', 'C', 'D', 'E', 'F']

🔍 Décryptage ligne par ligne

vus = {depart}On marque le départ tout de suite. vus est un ensemble : le test v not in vus y coûte

O (1)

file = deque([depart])La réserve, initialisée au départ. C'est une file : on ajoute en fin (append), on retire en tête (popleft).

s = file.popleft()Le cœur du BFS. On retire le sommet le plus ancien : c'est la règle FIFO qui garantit qu'on traite les sommets par distance croissante.

if v not in vus:On n'enfile que l'inconnu. Sans ce test, un cycle ferait boucler le parcours à l'infini.

vus.add(v)Marquer à la RENCONTRE, pas au traitement. Point subtil : on marque v dès qu'on l'enfile, pas quand on le sortira. Sinon un même sommet, voisin de plusieurs autres, serait enfilé plusieurs fois.

Trace du BFS depuis A — état à chaque tour de boucle
Sommet sorti `s`	Voisins ajoutés	File après	`ordre` après
—	(départ A)	[A]	[]
A	B, C	[B, C]	[A]
B	D, E	[C, D, E]	[A, B]
C	F	[D, E, F]	[A, B, C]
D	— (B vu)	[E, F]	[A, B, C, D]
E	— (B, F vus)	[F]	[A, B, C, D, E]
F	— (C, E vus)	[]	[A, B, C, D, E, F] ✓

📝 On voit les « cercles ». A (distance 0), puis B, C (distance 1), puis D, E, F (distance 2) : le BFS sort les sommets exactement dans l'ordre de leur distance au départ. C'est ce qui en fait l'outil du plus court chemin.

Plus court chemin en nombre d'arêtes

En mémorisant, pour chaque sommet, la distance du sommet dont on l'a découvert plus un, le BFS calcule la distance (nombre d'arêtes) du départ à tous les sommets.

def distances(g, depart):
    dist = {depart: 0}
    file = deque([depart])
    while file:
        s = file.popleft()
        for v in g[s]:
            if v not in dist:            # "pas encore de distance" = pas encore vu
                dist[v] = dist[s] + 1    # un pas de plus que s
                file.append(v)
    return dist

print(distances(g, "A"))   # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 2}

🔍 Décryptage ligne par ligne

dist = {depart: 0}Le dictionnaire des distances joue aussi le rôle de vus : « avoir une distance » = « avoir été vu ». Le départ est à distance 0.

if v not in dist:Première découverte de v. Comme le BFS découvre les sommets par distance croissante, la première fois qu'on atteint v, c'est par un plus court chemin.

dist[v] = dist[s] + 1Un pas de plus. v est voisin de s, donc à une arête de plus que s du départ. On fige cette distance, définitive.

Propriété 2.1 — BFS et plus court chemin ★ À savoir démontrer

Dans un graphe non pondéré, le parcours en largeur depuis un sommet $s$ découvre les sommets par distance croissante à $s$ . La valeur dist[v] calculée ci-dessus est le nombre minimal d'arêtes d'un chemin de $s$ à $v$ .

Démonstration

Montrons par récurrence sur $k$ que, à tout instant, la file contient uniquement des sommets de distance $k$ ou $k + 1$ (pour un certain $k$ ), les sommets de distance $k$ étant devant. Plus simplement, montrons la propriété clé : les sommets sont retirés de la file par distance réelle croissante, et dist[v] vaut cette distance.

Initialisation. Seul $s$ est dans la file, avec dist[s] = 0, qui est bien sa distance à lui-même.

Hérédité. Supposons que tout sommet déjà retiré $u$ l'a été avec dist[u] égal à sa vraie distance $δ (u)$ , et que la file est ordonnée par distance croissante. Quand on retire $s^{'}$ (de distance $d = δ (s^{'})$ ) et qu'on découvre un voisin $v$ encore sans distance, on pose dist[v] = d + 1. Ce $v$ est à distance au plus $d + 1$ (il est voisin de $s^{'}$ ). Il ne peut pas être plus proche : s'il existait un chemin de longueur $\leq d$ vers $v$ , son avant-dernier sommet, de distance $< d$ , aurait déjà été retiré avant $s^{'}$ (file ordonnée) et aurait découvert $v$ plus tôt — contradiction avec « $v$ sans distance ». Donc $δ (v) = d + 1$ , et comme $v$ est enfilé après tous les sommets de distance $d$ , la file reste ordonnée. $■$

3. Parcours en profondeur (DFS) — la récursion (ou la pile)

Le parcours en profondeur fait l'inverse : depuis un sommet, il plonge dans le premier voisin inconnu, puis dans le premier voisin inconnu de celui-ci, et ne revient en arrière que lorsqu'il est bloqué. C'est exactement le comportement de la récursion.

def dfs(g, depart):
    vus = set()
    ordre = []
    def explore(s):
        vus.add(s)
        ordre.append(s)
        for v in g[s]:
            if v not in vus:
                explore(v)     # on plonge dans v avant de continuer
    explore(depart)
    return ordre

print(dfs(g, "A"))   # ['A', 'B', 'D', 'E', 'F', 'C']

🔍 Décryptage ligne par ligne

def explore(s):Une fonction récursive interne. Elle traite s, puis s'appelle sur chaque voisin inconnu. vus et ordre, définis à l'extérieur, sont partagés entre tous les appels.

vus.add(s)
ordre.append(s)

On visite s dès l'entrée dans explore : marqué vu, ajouté à l'ordre.

if v not in vus: explore(v)La plongée. Dès qu'un voisin v est inconnu, on l'explore immédiatement et complètement avant de regarder le voisin suivant de s. C'est ce « tout de suite et à fond » qui fait la profondeur.

explore(depart)On amorce le parcours au sommet de départ. La pile d'appels de Python joue le rôle de la réserve.

Trace du DFS récursif depuis A — pile d'appels (indentation = profondeur)
Étape	Appel	Action	`ordre` après
1	explore(A)	visite A ; voisin B inconnu → plonge	[A]
2	explore(B)	visite B ; voisin D inconnu → plonge	[A, B]
3	explore(D)	visite D ; seul voisin B vu → remonte	[A, B, D]
4	explore(E)	de retour dans B : E inconnu → plonge ; visite E	[A, B, D, E]
5	explore(F)	voisin F de E inconnu → plonge ; visite F	[A, B, D, E, F]
6	explore(C)	voisin C de F inconnu → plonge ; visite C	[A, B, D, E, F, C] ✓

📝 BFS ≠ DFS. Sur le même graphe et le même départ, le BFS donne [A, B, C, D, E, F] (par cercles) et le DFS [A, B, D, E, F, C] (par plongées). Le sommet C, voisin direct de A, est visité en 3^e par BFS mais en dernier par DFS, parce que le DFS est parti explorer toute la branche de B d'abord.

On peut aussi écrire le DFS sans récursion, en gérant explicitement une pile (utile si le graphe est grand, pour éviter de saturer la pile d'appels de Python).

def dfs_iteratif(g, depart):
    vus = set()
    pile = [depart]         # reserve : une PILE
    ordre = []
    while pile:
        s = pile.pop()      # on retire le PLUS RECENT (LIFO)
        if s not in vus:
            vus.add(s)
            ordre.append(s)
            for v in g[s]:
                if v not in vus:
                    pile.append(v)
    return ordre

🔍 Décryptage ligne par ligne

pile = [depart]Une simple liste comme pile. On empile avec append, on dépile avec pop() (par la fin) — LIFO.

s = pile.pop()Le cœur du DFS itératif. On retire le sommet le plus récemment ajouté : c'est ce LIFO qui remplace la file du BFS et produit une exploration en profondeur.

if s not in vus:On teste au dépilage. Ici un sommet peut être empilé plusieurs fois (par plusieurs voisins) ; on le marque et le traite seulement à sa première sortie, on ignore les doublons ensuite.

⚠ Récursif et itératif : même parcours, pas forcément le même ordre exact. Le DFS itératif ci-dessus dépile le dernier voisin empilé en premier : selon qu'on empile les voisins dans l'ordre ou en sens inverse, l'ordre de visite peut légèrement différer de la version récursive. Les deux restent des parcours en profondeur valides — ce qui compte, c'est de plonger avant de revenir.

4. À quoi ça sert, et lequel choisir

📐 Ce qu'un parcours permet de faire.

Accessibilité / connexité : l'ensemble des sommets visités depuis $s$ est l'ensemble des sommets atteignables depuis $s$ . Si ce parcours atteint tous les sommets, le graphe est connexe.
Plus court chemin en nombre d'arêtes : uniquement le BFS (propriété 2.1).
Détection de cycle, tri des dépendances, exploration exhaustive : plutôt le DFS, qui suit les chemins jusqu'au bout.

Largeur (BFS) contre profondeur (DFS)
Critère	BFS (largeur)	DFS (profondeur)
Réserve	file (FIFO), `deque`	pile (LIFO) ou récursion
Ordre de visite	par distance croissante	par plongées successives
Plus court chemin (nb d'arêtes)	oui	non
Complexité	$O (n + m)$	$O (n + m)$
Usage typique	distances, diffusion	cycles, connexité, backtracking

💡 Même coût pour les deux. Chaque sommet est traité une fois, et chaque arête est examinée (deux fois, une par extrémité). Le coût total est donc

O (n + m)

pour BFS comme pour DFS, avec une représentation par listes d'adjacence. C'est optimal : on ne peut pas parcourir un graphe sans en lire au moins les sommets et les arêtes.

🎯 Accompagnement Majorant

Savoir choisir BFS ou DFS selon la question posée, c'est un réflexe qui rapporte gros. Nos mentors alumni X · Centrale · Mines t'entraînent sur les grands classiques (labyrinthe, composantes connexes, détection de cycle) pour que tu saches, d'un coup d'œil, quel parcours dégainer.

Trouver un mentor →

5. Exercices d'application

Fais-les sur papier (déroule file et pile !) avant d'ouvrir le corrigé, puis passe au quiz en bas de fiche.

Exo 1Dérouler un BFSFacile

Sur le graphe h = {1: [2, 3], 2: [1, 4], 3: [1, 4], 4: [2, 3]}, donne l'ordre de visite du parcours en largeur depuis le sommet 1, puis la distance de 1 à chaque sommet.

Voir la correction détaillée

File initiale [1]. On sort 1 → on ajoute 2, 3. File [2, 3], ordre [1].

On sort 2 → voisins 1 (vu), 4 (nouveau) → ajoute 4. File [3, 4], ordre [1, 2]. On sort 3 → voisins 1 (vu), 4 (vu). File [4], ordre [1, 2, 3]. On sort 4 → tout vu. Ordre final : [1, 2, 3, 4].

Distances : 1 → 0, 2 → 1, 3 → 1, 4 → 2 (on atteint 4 depuis 2, soit à 2 arêtes de 1).

Exo 2Compter les composantes connexesIntermédiaire

Écris est_connexe(g) qui renvoie True si le graphe (listes d'adjacence, supposé non vide) est connexe, c'est-à-dire si un parcours depuis un sommet atteint tous les sommets.

Voir la correction détaillée

On lance un parcours (BFS ou DFS) depuis un sommet quelconque, et on compare le nombre de sommets atteints au nombre total de sommets.

def est_connexe(g):
    depart = next(iter(g))       # un sommet quelconque
    atteints = set(bfs(g, depart))
    return len(atteints) == len(g)

Sur le graphe fil rouge, bfs(g, "A") atteint les 6 sommets, donc est_connexe(g) vaut True. Si un sommet était isolé, le parcours ne l'atteindrait pas et la fonction renverrait False.

Exo 3Y a-t-il un chemin entre deux sommets ?Difficile

Écris existe_chemin(g, u, v) qui renvoie True s'il existe un chemin de u à v. Indice : un parcours depuis u atteint exactement les sommets reliés à u.

Voir la correction détaillée

Un chemin de u à v existe si et seulement si v fait partie des sommets atteints par un parcours lancé depuis u.

def existe_chemin(g, u, v):
    return v in set(bfs(g, u))

# ou, sans construire tout l'ensemble, en s'arretant des qu'on trouve v :
def existe_chemin_v2(g, u, v):
    vus = {u}
    file = deque([u])
    while file:
        s = file.popleft()
        if s == v:
            return True
        for w in g[s]:
            if w not in vus:
                vus.add(w)
                file.append(w)
    return False

La seconde version s'arrête dès qu'elle rencontre v : inutile de finir le parcours. Sur le fil rouge, existe_chemin(g, "A", "F") vaut True (A–C–F ou A–B–E–F).

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu énoncer le squelette commun (vus + réserve + traiter les voisins inconnus) ?
Sais-tu que BFS utilise une file (FIFO) et DFS une pile ou la récursion ?
Sais-tu écrire le BFS avec deque et marquer les sommets à la rencontre ?
Sais-tu écrire le DFS récursif, et sa version itérative avec une pile ?
Sais-tu dérouler à la main un BFS et un DFS et obtenir des ordres différents ?
Sais-tu que le BFS calcule le plus court chemin en nombre d'arêtes, et pourquoi ?
Sais-tu utiliser un parcours pour tester l'accessibilité et la connexité ?
Sais-tu que BFS et DFS coûtent tous deux $O (n + m)$ avec des listes d'adjacence ?

À savoir refaire

BFS et plus court chemin — les sommets sont retirés par distance croissante, donc dist[v] est le nombre minimal d'arêtes de $s$ à $v$ .

Vue d'ensemble

Prérequis

1. Le squelette commun : marquer, mettre en réserve, traiter

2. Parcours en largeur (BFS) — la file

Plus court chemin en nombre d'arêtes

3. Parcours en profondeur (DFS) — la récursion (ou la pile)

4. À quoi ça sert, et lequel choisir

5. Exercices d'application

Récap final — Ce qu'il faut absolument retenir

À savoir refaire

Débloque la fiche complète

Quiz — Parcours de graphes

Fiches associées

Recherche par dichotomie

Variables, types et affectations

Conditions et booléens

Boucles for et while

Fonctions : paramètres et valeurs de retour

Listes et chaînes de caractères

Tu veux aller plus loin sur ce chapitre ?