Introduction : Pourquoi explorer un graphe ?
Imagine que tu doives trouver le chemin le plus court dans un labyrinthe, vérifier si un réseau social est connecté, ou parcourir un arbre de décisions. Dans tous ces cas, tu manipules une structure de données fondamentale : le graphe. En NSI, savoir explorer un graphe est une compétence clé. Deux stratégies s'opposent et se complètent : le Parcours en Largeur (BFS) et le Parcours en Profondeur (DFS). Dans cet article, on va décortiquer ces algorithmes, comprendre quand les utiliser et les coder en Python.
Les bases : Qu'est-ce qu'un graphe ?
Avant de plonger dans les parcours, assurons-nous de bien comprendre l'objet de notre étude. Un graphe est un ensemble de sommets (ou nœuds) reliés par des arêtes (ou arcs). On le note souvent G = (V, E).
- V : L'ensemble des sommets (ex: {A, B, C, D}).
- E : L'ensemble des arêtes, paires de sommets (ex: {(A,B), (B,C)}).
En Python, on peut le représenter de plusieurs façons. La plus intuitive pour nos algorithmes est le dictionnaire de listes d'adjacence.
Exemple de représentation :
graphe = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B'] }. Cela signifie que le sommet 'A' est relié à 'B' et 'C'.
Le Parcours en Profondeur (DFS - Depth-First Search)
Le principe du DFS est simple : « Vas aussi loin que possible le long d'une branche avant de revenir en arrière ». C'est une stratégie d'exploration récursive ou utilisant une pile (LIFO : Last In, First Out).
L'algorithme pas à pas
1. On part d'un sommet de départ. On le marque comme « visité ».
2. Pour chaque voisin de ce sommet qui n'a pas encore été visité, on applique récursivement le DFS.
3. On continue ainsi jusqu'à ce qu'il n'y ait plus de nouveaux sommets accessibles.
4. Si le graphe n'est pas connexe, on recommence depuis un sommet non visité.
Implémentation Python du DFS (version récursive)
def dfs(graphe, sommet, visites=None):
if visites is None:
visites = set()
visites.add(sommet)
print(sommet) # Traitement du sommet
for voisin in graphe[sommet]:
if voisin not in visites:
dfs(graphe, voisin, visites)
return visites
Cette fonction explore le graphe en « creusant » d'abord une branche. Son ordre de visite dépend de l'ordre des voisins dans les listes d'adjacence.
Le Parcours en Largeur (BFS - Breadth-First Search)
À l'opposé, le BFS suit la philosophie : « Explore tous les voisins proches avant d'aller plus loin ». Il explore le graphe par « couches » successives depuis le sommet de départ. Il utilise impérativement une file (FIFO : First In, First Out).
L'algorithme pas à pas
1. On part d'un sommet de départ. On l'ajoute à une file et on le marque comme visité.
2. Tant que la file n'est pas vide :
a. On retire le premier sommet de la file (on le « défile »).
b. On traite ce sommet.
c. Pour chacun de ses voisins non visités, on les marque comme visités et on les ajoute à la fin de la file (on les « enfile »).
3. Cela garantit de visiter tous les sommets à distance 1, puis distance 2, etc.
Implémentation Python du BFS
from collections import deque
def bfs(graphe, depart):
visites = set()
file = deque([depart])
visites.add(depart)
while file:
sommet = file.popleft()
print(sommet) # Traitement du sommet
for voisin in graphe[sommet]:
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
return visites
L'utilisation de deque de la bibliothèque standard est cruciale pour des opérations efficaces en début de file.
BFS vs DFS : Comparaison et cas d'usage
Ces deux algorithmes ne sont pas interchangeables. Leur choix dépend du problème à résoudre.
- BFS est idéal pour :
- Trouver le chemin le plus court (en nombre d'arêtes) entre deux sommets dans un graphe non pondéré.
- Explorer un graphe par « niveaux » (ex: propagation dans un réseau).
- DFS est idéal pour :
- Explorer toutes les possibilités (backtracking), comme dans un labyrinthe ou pour résoudre des puzzles.
- Tester la connexité, trouver des cycles, ou effectuer un tri topologique (dans un graphe orienté sans cycle).
- Parcourir des structures arborescentes (les arbres sont des graphes particuliers).
Complexité : Dans les deux cas, si le graphe est représenté par listes d'adjacence, la complexité temporelle est en O(|V| + |E|) (nombre de sommets + nombre d'arêtes). La complexité spatiale (mémoire) peut être différente : le DFS peut utiliser beaucoup de pile d'appels récursifs sur un graphe très profond, tandis que le BFS peut nécessiter une grande file pour un graphe très large.
Projet NSI : Implémente un solveur de labyrinthe
Pour mettre en pratique, voici une idée de projet : Crée un programme qui génère un labyrinthe sur une grille, puis trouve un chemin entre l'entrée et la sortie en utilisant BFS et DFS.
Représente ton labyrinthe comme un graphe où chaque cellule de la grille est un sommet, et où une arête existe si il n'y a pas de mur entre deux cellules adjacentes. Tu pourras :
1. Visualiser le labyrinthe.
2. Visualiser l'exploration en temps réel (les cases visitées par BFS et DFS).
3. Montrer que BFS trouve toujours le chemin le plus court, tandis que DFS peut trouver un chemin plus long mais plus rapidement dans certains cas.
4. Comparer les performances.
C'est un excellent projet pour ton portfolio NSI, qui combine structures de données, algorithmes et interface (avec PyGame ou Turtle par exemple).
