Retour au cours

Leçon 39 : Breadth First Search (BFS) : Concept et Implémentation

Algorithmes : De Zéro à Héro (Un Guide pour Débutants)

39. Breadth First Search (BFS - Recherche en Largeur)

Le BFS est un algorithme de parcours de graphe qui explore tous les nœuds voisins au niveau de profondeur actuel avant de passer aux nœuds du niveau de profondeur suivant.

Concept : Explorer par Couches

Imaginez des ondulations dans un étang. Le BFS explore couche par couche, trouvant tous les nœuds à un pas de distance, puis tous les nœuds à deux pas de distance, et ainsi de suite.

Le BFS utilise une Queue (File) pour garder une trace des nœuds à visiter ensuite, assurant une exploration niveau par niveau.

Étapes de l'Algorithme

  1. Commencer au nœud source S, marquer comme visité et l'enfiler (enqueue).
  2. Tant que la file n'est pas vide :
    • Défiler (dequeue) un nœud U.
    • Pour chaque voisin non visité V de U :
      • Marquer V comme visité et l'enfiler (enqueue V).

Cas d'Utilisation

  • Trouver le plus court chemin dans un graphe non pondéré (car il explore d'abord les nœuds les plus proches).
  • Robots d'exploration web (crawling niveau par niveau).