Qu'est-ce que l'algorithme BFS (Breadth-First Search)?
La recherche en largeur d'abord (BFS) est un algorithme utilisé pour représenter graphiquement des données ou rechercher des arbres ou des structures de traversée. 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 dans un graphique de manière précise dans le sens de la largeur. Cet algorithme 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é. 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.
Dans ce didacticiel sur l'algorithme, vous apprendrez:
- Qu'est-ce que l'algorithme BFS (Breadth-First Search)?
- Qu'est-ce que les traversées de graphes?
- L'architecture de l'algorithme BFS
- Pourquoi avons-nous besoin de l'algorithme BFS?
- Comment fonctionne l'algorithme BFS?
- Exemple d'algorithme BFS
- Règles de l'algorithme BFS
- Applications de l'algorithme BFS
Qu'est-ce que les traversées de graphes?
Un parcours de graphe est une méthodologie couramment utilisée pour localiser la position du sommet dans le graphe. C'est 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 vous permet de visiter rapidement chaque nœud d'un graphe sans être verrouillé dans une boucle infinie.
L'architecture de l'algorithme BFS
- Dans les différents niveaux de données, vous pouvez marquer n'importe quel nœud comme nœud de départ ou initial à parcourir. Le BFS visitera le nœud et le marquera comme visité et le placera dans la file d'attente.
- Maintenant, 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.
- De manière similaire, les nœuds les plus proches et non visités restants 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 en tant que 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 vitaux qui font de cet algorithme votre premier choix sont:
- BFS est utile pour analyser les nœuds dans un graphe et construire le chemin le plus court pour les traverser.
- BFS peut parcourir un graphe dans le plus petit nombre d'itérations.
- L'architecture de l'algorithme BFS est simple et robuste.
- Le résultat de l'algorithme BFS possède 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 soit pris dans un problème de boucle infinie.
Comment fonctionne l'algorithme BFS?
Le parcours de graphe nécessite que l'algorithme visite, vérifie et / ou met à jour chaque nœud non visité dans une structure arborescente. Les parcours de graphe sont classés en fonction de l'ordre dans lequel ils visitent les nœuds sur le graphe.
L'algorithme BFS démarre l'opération à partir du premier nœud ou du nœud de départ dans un graphique et le parcourt en profondeur. Une fois qu'il a traversé avec succès le nœud initial, le prochain sommet non traversé du graphe est visité et marqué.
Par conséquent, vous pouvez dire que tous les nœuds adjacents au sommet actuel sont visités et traversés lors de la première itération. Une méthodologie de file d'attente simple est utilisée pour implémenter le fonctionnement d'un algorithme BFS et comprend les étapes suivantes:
Étape 1)
Chaque sommet ou nœud du graphe est connu. Par exemple, vous pouvez marquer le nœud comme V.
Étape 2)
Dans le cas où le sommet V n'est pas accédé, 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érez tous les sommets restants sur le graphe qui sont 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 déplacement sont répétées jusqu'à ce que tous les nœuds soient visités.
Règles de l'algorithme BFS
Voici des règles importantes pour l'utilisation de l'algorithme BFS:
- Une structure de données de file d'attente (FIFO-First in First Out) est utilisée 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 graphe et continue de les déposer comme terminé.
- BFS visite un nœud non visité adjacent, 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 graphe soient traversés avec succès et marqués comme terminés.
- Il n'y a pas de boucles causées par BFS lors de la traversée des données à partir de n'importe quel nœud.
Applications de l'algorithme BFS
Jetons un coup d'œil à certaines des applications réelles où une implémentation d'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.
- Crawlers Web: les moteurs de recherche ou les robots d'exploration Web peuvent facilement créer plusieurs niveaux d'index en utilisant BFS. La mise en œuvre de BFS commence à partir de la source, qui est la page Web, puis elle 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 de l'emplacement source.
- Diffusion réseau: un paquet diffusé est guidé par l'algorithme BFS pour trouver et atteindre tous les nœuds pour lesquels il a l'adresse.
Résumé
- Un parcours de graphe est un processus unique qui nécessite que l'algorithme visite, vérifie et / ou met à 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 dans un graphe et construire le chemin le plus court pour les traverser.
- L'algorithme parcourt le graphe 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 sur la base du premier entré, premier sorti. Par conséquent, l'élément placé en premier dans le graphique est d'abord supprimé et imprimé en conséquence.
- L'algorithme BFS ne peut jamais être 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.