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.
- 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
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
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.
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
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
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é.