Quelle est la différence entre un parcours en largeur et un parcours en profondeur d’un graphe ?
Réponse courte
La largeur visite les sommets par distance croissante depuis le départ, avec une file. La profondeur suit une branche aussi loin que possible puis revient aux choix précédents, avec une pile ou la récursion.
Comprendre
Deux stratégies d’exploration
Un parcours en largeur découvre d’abord le départ, puis ses voisins, puis les voisins encore inconnus de ceux-ci. Une file conserve l’ordre d’arrivée : on traite le plus ancien sommet en attente. Un parcours en profondeur avance dans une branche jusqu’à ne plus trouver de voisin non visité, puis revient en arrière ; la pile des appels récursifs réalise ce retour.
Un même graphe, deux traces
Considère les arêtes non orientées AB, AC, BD, CD et CE, et examine les voisins dans l’ordre donné par ces listes. Depuis A, la largeur traite A, B, C, D, E. Elle trouve E à deux arêtes, par A–C–E. En profondeur récursive, la trace de découverte est A, B, D, C, E ; le chemin de découverte vers E est alors plus long. L’ordre dépend aussi de l’ordre des voisins.
Choisir le bon parcours
La largeur garantit un chemin avec le moins d’arêtes dans un graphe non pondéré. La profondeur convient à une exploration complète ou à la détection de structures, mais son premier chemin vers une destination n’est pas forcément le plus court. Depuis un départ, les deux ne découvrent que les sommets accessibles ; plusieurs composantes nécessitent plusieurs départs pour couvrir tout le graphe.
Exemples
- Dans les listes A: B, C ; B: A, D ; C: A, D, E ; D: B, C ; E: C, la largeur depuis A traite A, B, C, D, E.
- Sur ce même graphe, le parcours récursif en profondeur découvre A, B, D, C, E et atteint E par A–B–D–C–E.
- Si un graphe orienté possède seulement P→Q et R→Q, un parcours depuis P atteint Q, mais pas R : l’arc ne se remonte pas à l’envers.
Pièges fréquents
- Utiliser une pile pour prétendre obtenir les niveaux en largeur change l’ordre de traitement : une file retire le sommet en attente depuis le plus longtemps.
- Croire que le premier chemin de profondeur est toujours minimal confond une exploration par branche avec la garantie de distance de la largeur.
Pourquoi ça marche
La file maintient ensemble les sommets de distance proche ; la pile favorise au contraire la poursuite du dernier chemin commencé.
