Algorithme de recherche en largeur d'abord (BFS) avec EXEMPLE

Qu'est-ce que l'algorithme BFS (recherche en largeur d'abord) ?

La recherche en largeur d'abord (BFS) est un algorithme utilisé pour représenter graphiquement des données, rechercher des arbres ou traverser des structures. La forme complète de BFS est la recherche en largeur d'abord.

L'algorithme visite et marque efficacement tous les nœuds clés d'un graphique de manière précise dans le sens de l'étendue. Cet algorithme sélectionne un seul nœud (point initial ou source) dans un graphe puis visite tous les nœuds adjacents au nœud sélectionné. N'oubliez pas que BFS accède à ces nœuds un par un.

Une fois que l'algorithme visite et marque le nœud de départ, il se déplace vers les nœuds non visités les plus proches et les analyse. Une fois visités, tous les nœuds sont marqués. Ces itérations se poursuivent jusqu'à ce que tous les nœuds du graphe aient été visités et marqués avec succès.

Qu'est-ce que les parcours graphiques ?

Un parcours de graphique est une méthodologie couramment utilisée pour localiser la position du sommet dans le graphique. Il s'agit d'un algorithme de recherche avancé qui peut analyser le graphique avec rapidité et précision tout en marquant la séquence des sommets visités. Ce processus permet de visiter rapidement chaque nœud d'un graphique sans être enfermé dans une boucle infinie.

L'architecture de l'algorithme BFS

1. Dans les différents niveaux de données, vous pouvez marquer n'importe quel nœud comme nœud de départ ou initial pour commencer le parcours. Le BFS visitera le nœud, le marquera comme visité et le placera dans la file d'attente.
2. Désormais, le BFS visitera les nœuds les plus proches et non visités et les marquera. Ces valeurs sont également ajoutées à la file d'attente. La file d'attente fonctionne sur le Modèle FIFO.
3. De la même manière, les nœuds restants les plus proches et non visités sur le graphique sont analysés, marqués et ajoutés à la file d'attente. Ces éléments sont supprimés de la file d'attente lors de leur réception et imprimés en conséquence.

Pourquoi avons-nous besoin de l’algorithme BFS ?

Il existe de nombreuses raisons d'utiliser l'algorithme BFS pour rechercher votre ensemble de données. Certains des aspects les plus essentiels qui font de cet algorithme votre premier choix sont :

• BFS est utile pour analyser les nœuds d’un graphique et construire le chemin le plus court pour les parcourir.
• BFS peut parcourir un graphique en le plus petit nombre d'itérations.
• L'architecture de l'algorithme BFS est simple et robuste.
• Le résultat de l’algorithme BFS présente un haut niveau de précision par rapport à d’autres algorithmes.
• Les itérations BFS sont transparentes et il n'y a aucune possibilité que cet algorithme se retrouve pris dans un problème de boucle infinie.

Comment fonctionne l’algorithme BFS ?

Le parcours graphique nécessite que l'algorithme visite, vérifie et/ou mette à jour chaque nœud non visité dans une structure arborescente. Les parcours de graphique sont classés selon l'ordre dans lequel ils visitent les nœuds du graphique.

L'algorithme BFS démarre l'opération à partir du premier nœud ou nœud de départ d'un graphique et le parcourt minutieusement. Une fois qu'il traverse avec succès le nœud initial, le prochain sommet non parcouru du graphique est visité et marqué.

Par conséquent, vous pouvez dire que tous les nœuds adjacents au sommet actuel sont visités et parcourus lors de la première itération. Une méthodologie de file d'attente simple est utilisée pour mettre en œuvre le fonctionnement d'un algorithme BFS et comprend les étapes suivantes :

Étape 1)

Chaque sommet ou nœud du graphique est connu. Par exemple, vous pouvez marquer le nœud comme V.

Étape 2)

Si le sommet V n'est pas accessible, ajoutez le sommet V dans la file d'attente BFS.

Étape 3)

Démarrez la recherche BFS et, une fois terminée, marquez le sommet V comme visité.

Étape 4)

La file d'attente BFS n'est toujours pas vide, supprimez donc le sommet V du graphe de la file d'attente.

Étape 5)

Récupérer tous les sommets restants du graphique adjacents au sommet V

Étape 6)

Pour chaque sommet adjacent, disons V1, au cas où il ne serait pas encore visité, ajoutez V1 à la file d'attente BFS

Étape 7)

BFS visitera la V1, la marquera comme visitée et la supprimera de la file d'attente.

Exemple d'algorithme BFS

Étape 1)

Vous avez un graphique de sept nombres allant de 0 à 6.

Étape 2)

0 ou zéro a été marqué comme nœud racine.

Étape 3)

0 est visité, marqué et inséré dans la structure de données de la file d'attente.

Étape 4)

Les 0 nœuds adjacents et non visités restants sont visités, marqués et insérés dans la file d'attente.

Étape 5)

Les itérations de parcours sont répétées jusqu'à ce que tous les nœuds soient visités.

Règles de l'algorithme BFS

Voici les règles importantes pour l’utilisation de l’algorithme BFS :

• Une file d'attente (FIFO-First in First Out) Structure de données est utilisé par BFS.
• Vous marquez n'importe quel nœud du graphique comme racine et commencez à parcourir les données à partir de celui-ci.
• BFS parcourt tous les nœuds du graphique et continue de les supprimer une fois terminés.
• BFS visite un nœud adjacent non visité, le marque comme terminé et l'insère dans une file d'attente.
• Supprime le sommet précédent de la file d'attente au cas où aucun sommet adjacent n'est trouvé.
• L'algorithme BFS itère jusqu'à ce que tous les sommets du graphique soient parcourus avec succès et marqués comme terminés.
• Il n'y a aucune boucle provoquée par BFS lors du parcours des données depuis n'importe quel nœud.

Applications de l'algorithme BFS

Jetons un coup d'œil à certaines des applications réelles dans lesquelles la mise en œuvre d'un algorithme BFS peut être très efficace.

• Graphiques non pondérés : L'algorithme BFS peut facilement créer le chemin le plus court et un arbre couvrant minimum pour visiter tous les sommets du graphique dans les plus brefs délais avec une grande précision.
• Réseaux P2P : BFS peut être implémenté pour localiser tous les nœuds les plus proches ou voisins dans un réseau peer to peer. Cela permettra de trouver les données requises plus rapidement.
• Robots d'exploration Web : Les moteurs de recherche ou les robots d'exploration Web peuvent facilement créer plusieurs niveaux d'index en utilisant BFS. L'implémentation de BFS commence à partir de la source, qui est la page Web, puis visite tous les liens de cette source.
• Systèmes de navigation : BFS peut aider à trouver tous les emplacements voisins à partir de l’emplacement principal ou source.
• Diffusion en réseau : Un paquet diffusé est guidé par l'algorithme BFS pour trouver et atteindre tous les nœuds pour lesquels il possède l'adresse.

Résumé

• Un parcours de graphe est un processus unique qui nécessite que l'algorithme visite, vérifie et/ou mette à jour chaque nœud non visité dans une structure arborescente. L'algorithme BFS fonctionne sur un principe similaire.
• L'algorithme est utile pour analyser les nœuds d'un graphique et construire le chemin le plus court pour les parcourir.
• L'algorithme parcourt le graphique dans le plus petit nombre d'itérations et dans le temps le plus court possible.
• BFS sélectionne un seul nœud (point initial ou source) dans un graphique puis visite tous les nœuds adjacents au nœud sélectionné. BFS accède à ces nœuds un par un.
• Les données visitées et marquées sont placées dans une file d'attente par BFS. Une file d'attente fonctionne selon le principe du premier entré, premier sorti. Par conséquent, l’élément placé en premier dans le graphique est supprimé en premier et imprimé en conséquence.
• L’algorithme BFS ne peut jamais se retrouver pris dans une boucle infinie.
• En raison de sa haute précision et de sa mise en œuvre robuste, BFS est utilisé dans plusieurs solutions réelles telles que les réseaux P2P, les robots d'exploration Web et la diffusion réseau.