Algorithme de recherche en largeur d'abord (BFS) avec EXEMPLE
Sarah Chen
⚡ Résumé intelligent
La recherche en largeur (BFS) est un algorithme qui parcourt un graphe niveau par niveau, en visitant tous les voisins d'un nœud avant de descendre plus profondément. Il utilise une file FIFO et trouve le chemin le plus court dans les graphes non pondérés sans boucle infinie.
Qu'est-ce que l'algorithme BFS (recherche en largeur d'abord) ?
La recherche en largeur (BFS) est un algorithme utilisé pour explorer des données graphiques, parcourir un arbre ou explorer des structures. BFS signifie « recherche en largeur ».
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
- Dans les différents niveaux de données, vous pouvez désigner n'importe quel nœud comme nœud de départ ou nœud initial pour commencer le parcours. L'algorithme de parcours en largeur (BFS) visitera ce nœud, le marquera comme visité et l'ajoutera à la file d'attente.
- Le parcours en largeur (BFS) va maintenant visiter les nœuds les plus proches et non visités, puis les marquer. Ces valeurs sont également ajoutées à la file d'attente. La file d'attente fonctionne selon le principe suivant : Modèle FIFO.
- De la même manière, les nœuds les plus proches et non visités restants sur le graphe sont analysés, marqués et ajoutés à la file d'attente. Ces éléments sont retirés de la file d'attente au fur et à mesure de leur réception et affichés comme résultat.
Pourquoi avons-nous besoin de l’algorithme BFS ?
Il existe de nombreuses raisons d'utiliser l'algorithme BFS pour la recherche dans vos données. Voici quelques-uns des aspects les plus importants qui font de cet algorithme le choix idéal :
- 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é.
On peut donc affirmer que tous les nœuds adjacents au sommet courant sont visités et parcourus lors de la première itération. Un système de file d'attente simple est utilisé pour implémenter l'algorithme de parcours en largeur (BFS), et il 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 accédé, ajoutez-le à la file d'attente BFS.
Étape 3)
Lancez 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érez tous les sommets restants du graphe qui sont adjacents au sommet V.
Étape 6)
Pour chaque sommet adjacent, disons V1, s'il n'a pas encore été visité, ajoutez V1 à la file d'attente BFS.
Étape 7)
BFS visitera V1, le marquera comme visité et le 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 nœuds adjacents à 0 restants et non visités 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 – Premier entré, premier sorti) Structure de données est utilisé par BFS.
- Vous désignez n'importe quel nœud du graphe comme racine et vous commencez à parcourir les données à partir de ce nœud.
- Le parcours en largeur (BFS) parcourt tous les nœuds du graphe et omet les éléments manquants.ping les 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.
- Elle supprime le sommet précédent de la file d'attente si aucun sommet adjacent n'est trouvé.
- L'algorithme BFS itère jusqu'à ce que tous les sommets du graphe 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 minimal pour visiter tous les sommets du graphe dans les plus brefs délais et avec une grande précision.
- Réseaux P2P : L'algorithme BFS peut être utilisé pour localiser tous les nœuds les plus proches ou voisins dans un réseau pair à pair. Cela permet de trouver les données recherchées 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.
