Structure des données - Largeur de la première traversée

L'algorithme BFS (Breadth First Search) parcourt un graphe dans un mouvement vers la largeur et utilise une file d'attente pour se souvenir d'obtenir le sommet suivant pour démarrer une recherche, lorsqu'une impasse se produit dans une itération.

Comme dans l'exemple donné ci-dessus, l'algorithme BFS parcourt de A à B à E à F d'abord puis à C et G enfin à D. Il utilise les règles suivantes.

  • Rule 1- Visitez le sommet non visité adjacent. Marquez-le comme visité. Affichez-le. Insérez-le dans une file d'attente.

  • Rule 2 - Si aucun sommet adjacent n'est trouvé, supprimez le premier sommet de la file d'attente.

  • Rule 3 - Répétez la règle 1 et la règle 2 jusqu'à ce que la file d'attente soit vide.

Étape Traversée La description
1 Initialisez la file d'attente.
2 Nous commençons par visiter S (nœud de départ) et marquez-le comme visité.
3 Nous voyons alors un nœud adjacent non visité de S. Dans cet exemple, nous avons trois nœuds mais nous choisissons par ordre alphabétiqueA, marquez-le comme visité et mettez-le en file d'attente.
4 Ensuite, le nœud adjacent non visité de S est B. Nous le marquons comme visité et le mettons en file d'attente.
5 Ensuite, le nœud adjacent non visité de S est C. Nous le marquons comme visité et le mettons en file d'attente.
6 Maintenant, Sest laissé sans nœuds adjacents non visités. Alors, nous sortons de la file d'attente et trouvonsA.
sept De A nous avons Den tant que nœud adjacent non visité. Nous le marquons comme visité et le mettons en file d'attente.

À ce stade, il ne nous reste aucun nœud non marqué (non visité). Mais selon l'algorithme, nous continuons à retirer la file d'attente afin d'obtenir tous les nœuds non visités. Lorsque la file d'attente est vidée, le programme est terminé.

L'implémentation de cet algorithme en langage de programmation C peut être vue ici .