Visualiseur BFS vs DFS

Les algorithmes de traversée de graphiques sont strictement définis par leurs dépendances de structure de données : files d'attente pour la recherche en largeur d'abord (BFS) et piles pour la recherche en profondeur (DFS). BFS s'étend radialement, garantissant mathématiquement le chemin non pondéré le plus court, tandis que DFS sonde la profondeur maximale avant un retour en arrière récursif. La complexité temporelle pour les deux reste strictement limitée par O(V + E). Ces protocoles de traversée déterministes dictent l’efficacité informatique de l’analyse de réseau.

En les lançant côte à côte, on remarque une chose : elles visitent exactement les mêmes nœuds et les mêmes arêtes, mais dans un ordre différent. Le parcours en largeur (BFS) explore tout le voisinage courant avant d'aller plus loin, il doit donc mémoriser chaque nœud en attente sur la frontière. Le parcours en profondeur (DFS) s'engage sur une branche et ne suit que le chemin en cours. À retenir : privilégiez le BFS quand la réponse est sans doute proche, et le DFS quand le graphe est profond et que la mémoire doit rester réduite.

Bien avant les ordinateurs, le DFS existait comme une règle pour parcourir les labyrinthes, publiée par le mathématicien français Charles Pierre Trémaux au XIX^e siècle. Le BFS est arrivé bien plus tard : Edward F. Moore l'a réinventé dans un article de 1959 intitulé littéralement The Shortest Path Through a Maze, et Konrad Zuse l'avait déjà esquissé en 1945. Deux piliers de l'informatique, tous deux conçus au départ pour sortir d'un labyrinthe.