Pour mieux illustrer la différence entre "BFS" et "DFS", considérons un labyrinthe décrit par le plan de la figure 10.15.
Le graphe correspondant est obtenu en plaçant un sommet en chaque point du labyrinthe où il y a plus d'un chemin possible et, ensuite, en connectant les sommets conformément à l'architecture du labyrinthe. On obtient alors le graphe de la figure 10.16.
Dans la figure 10.17, on voit les sommets et les arcs parcourus alors que l'algorithme de Depth-First-Search est à mi-chemin dans le graphe du labyrinthe, ayant pris son départ dans le coin supérieur gauche.
La figure 10.18 représente la même situation mais obtenue par l'algorithme de Breadth-First-Search.
L'algorithme "DFS" explore le graphe en considérant les sommets les plus éloignés du point de départ et ne reprenant les sommets plus proches que lorsqu'un cul-de-sac est rencontré; c'est le type de parcours que fait un individu dans un labyrinthe car la prochaine place à explorer est toujours proche de l'endroit où il se trouve à un instant donné.
L'algorithme "BFS" couvre toute la région proche du point de départ, poursuivant plus loin seulement lorsque toutes les possibilités avoisinantes ont été explorées; c'est le type de parcours que fait un groupe de personnes qui se dirigent simultanément dans toutes les directions.
Mises à part ces considérations opérationnelles, il est intéressant de faire ressortir les différences fondamentales des deux méthodes :
11.
Structures récursives non linéaires: les graphes
orientés
Site Hosting: Bronco
Table des
matières.