Tout ce que vous devez savoir sur l'algorithme de recherche Breadth First



Dans ce blog sur l'algorithme de recherche en largeur d'abord, nous discuterons de la logique derrière les méthodes de traversée de graphes et comprendrons le fonctionnement de celles-ci.

Les méthodes Graph Traversal m'ont toujours assez fasciné. De la communication efficace entre pairs à la recherche des restaurants et des cafés les plus proches à l'aide du GPS, les méthodes de traversée ont un ensemble varié d'applications dans le scénario du monde réel. Dans ce blog sur l'algorithme de recherche en largeur d'abord, nous discuterons de la logique des méthodes de traversée de graphe et utiliserons des exemples pour comprendre le fonctionnement de l'algorithme de recherche en largeur d'abord.

Pour acquérir une connaissance approfondie de l'intelligence artificielle et de l'apprentissage automatique, vous pouvez vous inscrire en direct par Edureka avec une assistance 24/7 et un accès à vie.





Voici une liste de sujets qui seront couvert dans ce blog:

  1. Introduction à la traversée graphique
  2. Qu'est-ce que la recherche en largeur d'abord?
  3. Comprendre l'algorithme de recherche en largeur d'abord avec un exemple
  4. Pseudocode d'algorithme de recherche en largeur d'abord
  5. Applications de la recherche en largeur d'abord

Introduction à la traversée graphique

Le processus de visite et d'exploration d'un graphe à traiter est appelé parcours de graphe. Pour être plus précis, il s'agit de visiter et d'explorer chaque sommet et chaque arête d'un graphe de sorte que tous les sommets soient explorés exactement une fois.



Cela semble simple! Mais il y a un hic.

Il existe plusieurs techniques de parcours de graphe telles que la recherche en largeur d'abord, la première recherche en profondeur, etc. Le défi est d'utiliser un graphique technique de traversée la plus appropriée pour résoudre un problème particulier. Cela nous amène à la technique de recherche en largeur d'abord.

Qu'est-ce que l'algorithme de recherche en largeur d'abord?

L'algorithme de recherche en largeur d'abord est une technique de traversée de graphe, dans laquelle vous sélectionnez un nœud initial aléatoire (nœud source ou racine) et commencez à parcourir le graphe par couche de manière à ce que tous les nœuds et leurs nœuds enfants respectifs soient visités et explorés.



Avant d'aller plus loin et de comprendre la recherche en largeur d'abord avec un exemple, familiarisons-nous avec deux termes importants liés au parcours de graphe:

Traversée des graphes - Algorithme de recherche en largeur d

  1. Visiter un nœud: Tout comme son nom l'indique, visiter un nœud signifie visiter ou sélectionner un nœud.
  2. Explorer un nœud: Explorer le nœuds adjacents (nœuds enfants) d'un nœud sélectionné.

Reportez-vous à la figure ci-dessus pour mieux comprendre cela.

Comprendre l'algorithme de recherche en largeur d'abord avec un exemple

L'algorithme de recherche en largeur d'abord suit une approche simple basée sur les niveaux pour résoudre un problème. Considérez l'arbre binaire ci-dessous (qui est un graphique). Notre objectif est de parcourir le graphique en utilisant l'algorithme de recherche en largeur d'abord.

Avant de commencer, vous devez vous familiariser avec la structure de données principale impliquée dans l'algorithme de recherche en largeur d'abord.

Une file d'attente est une structure de données abstraite qui suit la méthodologie First-In-First-Out (les données insérées en premier seront accessibles en premier). Il est ouvert aux deux extrémités, où une extrémité est toujours utilisée pour insérer des données (mise en file d'attente) et l'autre est utilisée pour supprimer des données (dequeue).

Examinons maintenant les étapes à suivre pour parcourir un graphique à l'aide de la recherche en largeur d'abord:

Étape 1: Prenez une file d'attente vide.

Étape 2: Sélectionnez un nœud de départ (visitant un nœud) et insérez-le dans la file d'attente.

Étape 3: À condition que la file d'attente ne soit pas vide, extrayez le nœud de la file d'attente et insérez ses nœuds enfants (en explorant un nœud) dans la file d'attente.

Étape 4: Imprimez le nœud extrait.

Ne vous inquiétez pas si vous êtes confus, nous comprendrons cela avec un exemple.

Jetez un œil au graphique ci-dessous, nous utiliserons l'algorithme de recherche en largeur d'abord pour parcourir le graphique.

Dans notre cas, nous allons attribuer le nœud «a» comme nœud racine et commencer à traverser vers le bas et suivre les étapes mentionnées ci-dessus.

L'image ci-dessus illustre le processus de bout en bout de l'algorithme de recherche en largeur d'abord. Laissez-moi vous expliquer cela plus en profondeur.

  1. Attribuez «a» comme nœud racine et insérez-le dans la file d’attente.
  2. Extrayez le nœud «a» de la file d'attente et insérez les nœuds enfants de «a», c'est-à-dire «b» et «c».
  3. Imprimer le nœud «a».
  4. La file d’attente n’est pas vide et comporte les nœuds «b» et «c». Puisque «b» est le premier nœud de la file d’attente, extrayons-le et insérons les nœuds enfants de «b», c’est-à-dire les nœuds «d» et «e».
  5. Répétez ces étapes jusqu'à ce que la file d'attente soit vide. Notez que les nœuds déjà visités ne doivent pas être ajoutés à la file d'attente encore.

Examinons maintenant le pseudocode de l'algorithme de recherche en largeur d'abord.

Pseudocode d'algorithme de recherche en largeur d'abord

Voici le pseudo-code pour implémenter l'algorithme de recherche en largeur d'abord:

Entrée: s en tant que noeud source BFS (G, s) laisse Q être en file d'attente. Q.enqueue (s) marque s comme visitée tandis que (Q n'est pas vide) v = Q.dequeue () pour tous les voisins w de v dans le graphique G si w n'est pas visité Q.enqueue (w) marque w comme visité

Dans le code ci-dessus, les étapes suivantes sont exécutées:

  1. (G, s) est entré, ici G est le graphe et s est le nœud racine
  2. Une file «Q» est créée et initialisée avec le nœud source «s»
  3. Tous les nœuds enfants de «s» sont marqués
  4. Extraire les 's' de la file d'attente et visiter les nœuds enfants
  5. Traiter tous les nœuds enfants de v
  6. Stocke w (nœuds enfants) dans Q pour visiter davantage ses nœuds enfants
  7. Continuez jusqu'à ce que 'Q' soit vide

Avant de terminer le blog, examinons quelques applications de l'algorithme de recherche en largeur d'abord.

Applications de l'algorithme de recherche en largeur d'abord

La recherche en largeur d'abord est une méthode simple de traversée de graphe qui a une gamme surprenante d'applications. Voici quelques façons intéressantes d'utiliser Bread-First Search:

Crawlers dans les moteurs de recherche: Breadth-First Search est l'un des principaux algorithmes utilisés pour l'indexation des pages Web. L'algorithme commence à parcourir à partir de la page source et suit tous les liens associés à la page. Ici, chaque page Web sera considérée comme un nœud dans un graphique.

Systèmes de navigation GPS: Breadth-First Search est l'un des meilleurs algorithmes utilisés pour trouver des emplacements voisins à l'aide du système GPS.

Trouvez le chemin le plus court et l'arbre couvrant minimum pour un graphique non pondéré: Lorsqu'il s'agit d'un graphe non pondéré, le calcul du chemin le plus court est assez simple car l'idée derrière le chemin le plus court est de choisir un chemin avec le moins d'arêtes. La recherche en largeur d'abord peut permettre cela en parcourant un nombre minimum de nœuds à partir du nœud source. De même, pour un arbre couvrant, nous pouvons utiliser l'une des deux méthodes de recherche en largeur d'abord ou de traversée en profondeur d'abord pour trouver un arbre couvrant.

Diffusion: La mise en réseau utilise ce que nous appelons des paquets pour la communication. Ces paquets suivent une méthode de traversée pour atteindre divers nœuds de réseau. L'une des méthodes de parcours les plus couramment utilisées est la recherche en largeur d'abord. Il est utilisé comme un algorithme utilisé pour communiquer des paquets diffusés sur tous les nœuds d'un réseau.

Réseautage d'égal à égal: La recherche en largeur d'abord peut être utilisée comme méthode de traversée pour trouver tous les nœuds voisins dans un réseau d'égal à égal. Par exemple, BitTorrent utilise Breadth-First Search pour la communication d'égal à égal.

Tout cela concernait le fonctionnement de l'algorithme de recherche en largeur d'abord. Maintenant que vous savez parcourir les graphiques, je suis sûr que vous êtes curieux d'en savoir plus. Voici quelques blogs pertinents pour vous intéresser:

  1. Introduction aux chaînes de Markov avec des exemples - Chaînes de Markov avec Python

Avec cela, nous arrivons à la fin de ce blog. Si vous avez des questions concernant ce sujet, veuillez laisser un commentaire ci-dessous et nous vous répondrons.

sauter en c ++

Si vous souhaitez vous inscrire à un cours complet sur l'intelligence artificielle et l'apprentissage automatique, Edureka a un Cela vous permettra de maîtriser des techniques telles que l'apprentissage supervisé, l'apprentissage non supervisé et le traitement du langage naturel. Il comprend une formation sur les dernières avancées et approches techniques de l'intelligence artificielle et de l'apprentissage automatique telles que l'apprentissage en profondeur, les modèles graphiques et l'apprentissage par renforcement.