Qu’est-ce que BFS ?
La recherche en largeur d'abord (BFS) est basée sur le passage des nœuds en ajoutant les voisins de chaque nœud à la file d'attente de parcours en commençant par le nœud racine. Le BFS d'un graphique est similaire à celui d'un arbre, à l'exception du fait que les graphiques peuvent avoir des cycles. Contrairement à la recherche en profondeur, tous les nœuds voisins à une profondeur donnée sont étudiés avant de passer au niveau suivant.
Algorithme BFS
Voici les étapes à suivre pour utiliser la recherche en largeur pour explorer un graphique :
- Prenez les données pour la matrice de contiguïté ou la liste de contiguïté du graphique.
- Créez une file d'attente et remplissez-la d'éléments.
- Activez le nœud racine (c'est-à-dire obtenez le nœud racine au début de la file d'attente).
- Retirez le début de la file d'attente (ou l'élément initial), puis mettez tous les nœuds proches de la file d'attente en file d'attente de gauche à droite. Retirez simplement la tête de file d'attente et reprenez l'opération si un nœud n'a pas de nœuds à proximité qui doivent être étudiés. (Remarque : si un voisin qui a déjà fait l'objet d'une enquête ou qui est dans la file d'attente émerge, ne le mettez pas en file d'attente ; ignorez-le plutôt.)
- Continuez ainsi jusqu'à ce que la file d'attente soit vide.
Applications BFS
En raison de la flexibilité de l'algorithme, la recherche en largeur d'abord est très utile dans le monde réel. En voici quelques-uns :
- Dans un réseau peer-to-peer, les nœuds homologues sont découverts. La plupart des clients torrent, tels que BitTorrent, uTorrent et qBittorent, utilisent ce processus pour trouver des « graines » et des « pairs » sur le réseau.
- L'index est construit à l'aide de techniques de traversée de graphiques lors de l'exploration du Web. La procédure commence avec la page source en tant que nœud racine et se poursuit jusqu'à toutes les pages secondaires liées à la page source (et ce processus se poursuit). En raison de la profondeur réduite de l'arbre de récursivité, la recherche en largeur d'abord présente ici un avantage inhérent.
- L'utilisation de systèmes de navigation GPS utilisant le GPS permet d'effectuer une recherche approfondie pour localiser les sites à proximité.
- La technique de Cheney, qui utilise le concept de recherche en largeur, est utilisée pour collecter les déchets.
Exemple de traversée BFS
Pour commencer, regardons un exemple simple. Nous allons commencer par 0 comme nœud racine et parcourir le graphique.
Étape 1: Mettre en file d'attente (0)
File d'attente
cout
| 0 |
Étape 2: Retirer la file d'attente (0), Mettre en file d'attente (1), Mettre en file d'attente (3), Mettre en file d'attente (4)
File d'attente
| 1 | 3 | 4 |
Étape 3: Dequeue(1), Enqueue(2)
File d'attente
| 3 | 4 | 2 |
Étape 4: Retirer la file d'attente (3), mettre en file d'attente (5). Nous n'ajouterons plus 1 à la file d'attente car 0 a déjà été exploré.
File d'attente
| 4 | 2 | 5 |
Étape 5 : Dequeue(4)
File d'attente
| 2 | 5 |
Étape 6 : Dequeue(2)
File d'attente
| 5 |
Étape 7 : Dequeue(5)
File d'attente
La file d'attente est vide maintenant, nous allons donc arrêter le processus.
Programme Java de recherche en largeur
Il existe plusieurs approches pour gérer le code. Nous discuterons principalement des étapes impliquées dans la mise en œuvre d’une recherche large en Java. Une liste de contiguïté ou une matrice de contiguïté peut être utilisée pour stocker des graphiques ; les deux méthodes sont acceptables. La liste de contiguïté sera utilisée pour représenter notre graphique dans notre code. Lors de l'implémentation de l'algorithme Breadth-First Search en Java, il est beaucoup plus facile de gérer la liste de contiguïté puisque nous n'avons qu'à parcourir la liste des nœuds attachés à chaque nœud une fois que le nœud est retiré de la file d'attente de la tête (ou du début) du file d'attente.
Le graphique utilisé pour démontrer le code sera identique à celui utilisé dans l'exemple précédent.
BFSTraversal.java
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>