Algorithme de parcours en largeur

L'algorithme de parcours en largeur commence à un nœud quelconque d’un graphe, parfois appelé "clé de recherche", et explore tous les nœuds voisins de même profondeur avant de passer aux nœuds situés au prochain niveau de profondeur. On pourrait le comparer à une "onde". 1️⃣️ On retire le premier élément entré dans notre liste de nœuds à explorer (FIFO) et on le traite. (Seulement la clé de recherche s'y trouve au démarrage) 2️⃣️ On indique que le nœud a été exploré, puis on ajoute, à la fin de notre liste de nœuds à explorer, tous les nœuds enfants non explorés. 3️⃣️ Si la liste à explorer n'est pas vide et que les conditions de fin ne sont pas remplies (élément recherché non trouvé par exemple), on répète l'étape 1.

Une pile est une liste avec gestion LIFO (Last In, First Out - Dernier entré, premier sortie), une file est une liste avec gestion FIFO (First In, First Out - Premier entré, premier sortie).

Si nous changeons le mode de gestion de la liste de FIFO à LIFO, alors nous transformons notre algorithme de parcours en largeur en algorithme de parcours en profondeur. (sans récursivité)

Si on doit vérifier qu'une connexion existe entre deux nœuds, alors l'algorithme de parcours en profondeur sera, en moyenne, plus performant. En revanche, si nous recherchons le plus court chemin, et si les nœuds sont équidistants alors l'algorithme de parcours en largeur sera meilleur. En effet, avec l'algorithme de parcours en profondeur, lorsque l'on tombe sur l'élément recherché, il peut exister un autre chemin plus court. Ce qui implique que l'ensemble des nœuds de l'arbre doit être parcouru.

L'algorithme de Dijkstra est une généralisation du parcours en largeur prenant en compte une pondération entre les nœuds (distance par exemple).