Concept
En général,
1. l'algoritme considère la case où il est
2. il regarde les murs autours de lui et en déduit les voisins qui lui sont accessibles
3. il fait la distinction entre les voisins qu'il a déjà vu et ceux qu'il ne connait pas
4. puis il décide, parmis les voisins qu'il ne connait pas, de les visiter en priorité dans le sens des aiguilles d'une montre.
Le système DFS et BFS se distinguent lorsqu'il y a un choix à faire (au milieu d'un couloir, ou à un carrefour).
* Le DFS (Depth First Search), en français "Recherche d'abord en profondeur" continue toujours dans une direction. S'il est bloqué à une impasse, il reviens au dernier carrefour.
L'avantage est que si la sortie se trouve sur le bon chemin, il y accède en "sprintant", mais il pedra du temps s'il ce chemin menait à une impasse…
ou s'il passe à côté de la sortie
* Le BFS (Breadth First Search), en français "Recherche d'abord en largeur" est plus "prudent" : il analyse chacun de ses voisins, puis les voisins de ses voisins, etc. jusqu'à trouver la sortie.
L'avantage est que si la sortie se trouve près de lui, il ne risque pas de passer à côté comme le DFS, par contre si la sortie est lointaine, il mettra beaucoup de temps.
Note pour les développeurs : le DFS et le BFS sont le même algoritme, l'un utilise une pile et l'autre une file, en Javascript j'ai écris
if(systeme==='DFS') v = arrCarreeAanalyser.pop()
if(systeme==='BFS') v = arrCarreeAanalyser.shift()