Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Parcourir un graphe consiste à visiter ses sommets de proche en proche. Deux stratégies sont au programme.
Le parcours en largeur (BFS, Breadth-First Search) explore le graphe niveau par niveau à l'aide d'une file (FIFO) : on visite d'abord tous les voisins directs de la source, puis leurs voisins, etc. Dans un graphe non pondéré, le BFS donne le plus court chemin en nombre d'arêtes.
Le parcours en profondeur (DFS, Depth-First Search) s'enfonce le plus loin possible avant de revenir en arrière (backtracking). Il utilise une pile (LIFO) ou, plus naturellement, la récursivité.
Dans les deux cas, il est indispensable de marquer les sommets visités (ensemble ou tableau de booléens) pour ne traiter chaque sommet qu'une fois et éviter de boucler sur les cycles.
Complexité (listes d'adjacence) : O(n + m) \quad (n \text{ sommets}, \ m \text{ arêtes}).
BFS en Python :
from collections import deque def parcours_largeur(g, depart): file = deque([depart]) visites = {depart} ordre = [] while file: s = file.popleft() ordre.append(s) for voisin in g[s]: if voisin not in visites: visites.add(voisin) file.append(voisin) return ordre
DFS récursif :
def parcours_profondeur(g, s, visites=None): if visites is None: visites = set() visites.add(s) ordre = [s] for voisin in g[s]: if voisin not in visites: ordre += parcours_profondeur(g, voisin, visites) return ordre
1. Choisir la structure : file pour BFS, pile/récursivité pour DFS. 2. Marquer la source avant d'entrer dans la boucle. 3. Marquer un voisin au moment de l'enfiler (BFS) pour éviter les doublons. 4. Pour la connexité ou l'accessibilité, regarder l'ensemble des sommets marqués à la fin.
list.pop(0) au lieu de deque.popleft() pour la file : O(n) inutile.BFS et DFS sont incontournables. Sachez dérouler à la main l'ordre de visite en respectant l'ordre des voisins indiqué par les listes d'adjacence, justifier la complexité O(n+m), et coder le parcours avec marquage des sommets visités. Reliez le BFS au plus court chemin dans un graphe non pondéré et le parcours à la détection de connexité ou d'accessibilité entre deux sommets. À l'épreuve pratique, la représentation est presque toujours un dictionnaire de listes d'adjacence, et l'on demande couramment de compléter une fonction de parcours, de compter les composantes connexes, ou de tester l'existence d'un chemin entre deux sommets. Soignez le moment du marquage : marquer un sommet dès qu'on l'enfile (BFS) évite de le traiter en double.