NSI (Spé) — Algorithmique
Algorithmes sur les graphes
Parcours en largeur (BFS), parcours en profondeur (DFS), algorithme de Dijkstra pour les plus courts chemins
Résumé synthétiqueFiche en 4 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Réseaux sociaux, GPS, plans de métro, pages web : tout cela, ce sont des graphes — des sommets reliés par des arêtes. Pour les explorer, deux parcours fondamentaux. Le parcours en largeur (BFS) avance par cercles concentriques depuis le départ à l'aide d'une file : il donne le plus court chemin en nombre d'arêtes (la plus courte chaîne d'amis, le moins de coups). Le parcours en profondeur (DFS) plonge le plus loin possible avant de revenir en arrière, via une pile ou la récursivité : idéal pour détecter les cycles et les composantes connexes. Quand les arêtes portent un poids (une distance, un temps), on passe à l'algorithme de Dijkstra, qui trouve le plus court chemin pondéré — à condition que tous les poids soient positifs. Tous ces parcours coûtent $O(n+m)$ avec des listes d'adjacence.
Le BFS explore le graphe par couches : d'abord les voisins directs du départ, puis leurs voisins, et ainsi de suite. Comme pour les arbres, il s'appuie sur une file — plus un ensemble de sommets visités, indispensable car un graphe peut contenir des cycles.
Depuis A : le BFS (file) explore par niveaux → A, B, C, D, E, F ; le DFS (pile) plonge en profondeur → A, B, D, E, C, F.
- Explore les sommets par distance croissante au départ : voisins directs, puis voisins des voisins.
- Outils : une file (FIFO) + un ensemble visités pour ne jamais retraiter un sommet.
- Algorithme : enfiler le départ et le marquer ; tant que la file n'est pas vide, défiler, traiter, enfiler les voisins non visités.
- Trouve le plus court chemin en nombre d'arêtes dans un graphe non pondéré.
- Complexité : $O(n+m)$ avec des listes d'adjacence (n sommets, m arêtes).
- Applications : plus court chemin dans un labyrinthe, nombre minimal de coups, distance dans un réseau social.
Exemple
from collections import deque
def bfs(graphe, depart):
visites = {depart}
file = deque([depart])
while file:
s = file.popleft()
for voisin in graphe[s]:
if voisin not in visites:
visites.add(voisin) # marquer dès l'enfilage
file.append(voisin)
return visites
def bfs(graphe, depart):
visites = {depart}
file = deque([depart])
while file:
s = file.popleft()
for voisin in graphe[s]:
if voisin not in visites:
visites.add(voisin) # marquer dès l'enfilage
file.append(voisin)
return visites
Piège à éviter
Marque un sommet comme visité au moment de l'enfiler, pas seulement au défilage. Sinon un même sommet peut être enfilé plusieurs fois par des voisins différents, ce qui fausse le parcours et gonfle la file.
Le DFS suit un chemin aussi loin que possible, puis revient en arrière (backtracking) dès qu'il est bloqué pour explorer une autre branche. Il s'écrit naturellement de façon récursive (la pile d'appels joue le rôle de pile), ou itérative avec une pile explicite.
- Plonge le plus profond possible avant de remonter explorer les branches non visitées.
- Version récursive : dfs(s) marque s, puis appelle dfs sur chaque voisin non visité.
- Version itérative : une pile (LIFO) remplace la file du BFS.
- Usages : détecter un cycle, trouver les composantes connexes, faire un tri topologique (graphe orienté acyclique).
- Complexité : $O(n+m)$ avec des listes d'adjacence — la même que BFS.
- Seule la structure (pile vs file) distingue DFS et BFS, mais l'ordre de visite diffère fortement.
Exemple
def dfs(graphe, s, visites=None):
if visites is None:
visites = set()
visites.add(s) # marquer s
for voisin in graphe[s]:
if voisin not in visites:
dfs(graphe, voisin, visites)
return visites
if visites is None:
visites = set()
visites.add(s) # marquer s
for voisin in graphe[s]:
if voisin not in visites:
dfs(graphe, voisin, visites)
return visites
Piège à éviter
Oublier de marquer les sommets visités provoque une boucle infinie dès qu'il y a un cycle : on tourne indéfiniment entre les mêmes sommets. Le marquage est ce qui distingue un parcours de graphe d'un parcours d'arbre.
Quand chaque arête a un poids (distance, durée, coût), le plus court chemin n'est plus celui qui a le moins d'arêtes, mais celui de poids total minimal. Dijkstra le calcule depuis une source en choisissant à chaque étape le sommet non visité le plus proche.
- Trouve le plus court chemin pondéré d'une source vers tous les autres sommets.
- Condition : tous les poids positifs ou nuls (sinon, utiliser Bellman-Ford).
- Principe : à chaque étape, choisir le sommet non visité de distance minimale, puis relâcher ses voisins.
- Relaxation : si dist[u] + poids(u, v) < dist[v], alors dist[v] = dist[u] + poids(u, v) et predecesseur[v] = u.
- Initialisation : dist[source] = 0 et dist[autres] = $+\infty$.
- Complexité : $O(n^2)$ avec un simple tableau, $O((n+m)\log n)$ avec une file de priorité (tas).
Exemple
# Relaxation, cœur de Dijkstra
if dist[u] + poids(u, v) < dist[v]:
dist[v] = dist[u] + poids(u, v)
predecesseur[v] = u
# On remonte ensuite les predecesseur[] pour reconstruire le chemin.
if dist[u] + poids(u, v) < dist[v]:
dist[v] = dist[u] + poids(u, v)
predecesseur[v] = u
# On remonte ensuite les predecesseur[] pour reconstruire le chemin.
Piège à éviter
Dijkstra échoue avec des poids négatifs : un sommet déjà figé comme « visité » pourrait voir apparaître plus tard un chemin plus court, jamais pris en compte. Pour des poids négatifs, il faut Bellman-Ford.
Ces trois algorithmes explorent un graphe, mais ne répondent pas à la même question. Choisir le bon, c'est d'abord identifier ce que l'on cherche : atteindre, ordonner, ou minimiser un coût.
- BFS : plus court chemin en nombre d'arêtes (graphe non pondéré). Utilise une file.
- DFS : exploration complète, cycles, composantes connexes, tri topologique. Utilise une pile ou la récursivité.
- Dijkstra : plus court chemin pondéré (poids positifs), par relaxation successive.
- Complexités : BFS et DFS en $O(n+m)$ ; Dijkstra en $O(n^2)$ ou $O((n+m)\log n)$.
- Pour un graphe non pondéré, BFS suffit : inutile de sortir Dijkstra.
- Si tous les poids valent 1, Dijkstra redonne exactement le résultat du BFS.
Exemple
Itinéraire GPS le plus court en distance : poids = kilomètres → Dijkstra. Plus courte chaîne d'amis dans un réseau social : arêtes non pondérées → BFS. Détecter une dépendance circulaire entre modules : DFS et recherche de cycle.
Piège à éviter
Erreur fréquente : appliquer Dijkstra sur un graphe non pondéré alors qu'un simple BFS donne le même plus court chemin plus simplement — ou, à l'inverse, utiliser BFS sur un graphe pondéré, où il ignore les poids et se trompe.
Quiz - Algorithmes sur les graphes
10 questions
S'entraîner
- Quiz : Algorithmes sur les graphes10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
Questions fréquentes
Les points clés à retenir sur Algorithmes sur les graphes, extraits du quiz de révision.
Quelle structure de données utilise le parcours en largeur (BFS) ?
Réponse :
Une file
BFS utilise une file (FIFO) pour explorer les sommets par distance croissante au sommet de départ.
Le parcours en profondeur (DFS) utilise :
Réponse :
Une pile (ou la récursivité)
DFS utilise une pile (LIFO) en version itérative, ou la pile d'appels de fonctions en version récursive, pour explorer le plus loin possible avant de revenir en arrière.
L'algorithme de Dijkstra ne fonctionne pas correctement avec :
Réponse :
Des poids négatifs
Dijkstra suppose que tous les poids sont positifs ou nuls. Avec des poids négatifs, un sommet déjà visité pourrait avoir un chemin plus court découvert plus tard, faussant le résultat.
BFS trouve le plus court chemin en :
Réponse :
Nombre d'arêtes (graphe non pondéré)
BFS explore les sommets par couches concentriques (distance 1, puis 2, etc.), trouvant ainsi le chemin avec le moins d'arêtes dans un graphe non pondéré.