Introduction à l'algorithme BFS
Pour accéder aux données et les gérer efficacement, elles peuvent être stockées et organisées dans un format spécial appelé structure de données. Il existe de nombreuses structures de données telles que pile, tableau, liste liée, files d'attente, arbres et graphiques, etc. Dans les structures de données linéaires, telles que pile, tableau, liste liée et file d'attente, les données sont organisées en ordre linéaire alors que, dans structures de données linéaires comme les arbres et les graphiques, les données sont organisées hiérarchiquement et non dans une séquence. Le graphique est une structure de données non linéaire qui a des nœuds et des bords. Les nœuds dans le graphique peuvent également être appelés sommets dont le nombre est fini et les arêtes sont les lignes de connexion entre deux nœuds.
Dans le graphique ci-dessus, les sommets peuvent être représentés par V = (A, B, C, D, E) et les arêtes peuvent être définies comme
E = (AB, AC, CD, BE)
Qu'est-ce que l'algorithme BFS?
Il existe généralement deux algorithmes utilisés pour parcourir un graphe. Il s'agit des algorithmes BFS (Breadth-First Search) et DFS (Depth First Search). La traversée du graphique se rend exactement une fois chaque sommet ou nœud et arête, dans un ordre bien défini. De plus, il est très important de garder une trace des sommets visités afin que le même sommet ne soit pas traversé deux fois. Dans l'algorithme Breath First Search, la traversée commence à partir d'un nœud sélectionné ou d'un nœud source et la traversée continue à travers les nœuds directement connectés au nœud source. En termes plus simples, dans l'algorithme BFS, il faut d'abord déplacer horizontalement et traverser la couche actuelle, après quoi la couche suivante doit être effectuée.
Comment fonctionne l'algorithme BFS?
Prenons l'exemple du graphique ci-dessous.
La tâche importante à accomplir est de trouver le chemin le plus court dans un graphique tout en traversant les nœuds. Lorsque nous traversons un graphe, le sommet passe de l'état non découvert à l'état découvert et devient finalement complètement découvert. Il est à noter qu'il est possible de rester bloqué à un moment donné en traversant un graphe et qu'un nœud peut être visité deux fois. Nous pouvons donc utiliser une méthode de marquage des nœuds après avoir changé l'état d'être non découvert en étant complètement découvert.
Nous pouvons voir dans l'image ci-dessous que les nœuds peuvent être marqués dans les graphiques lorsqu'ils deviennent complètement découverts en les marquant en noir. Nous pouvons commencer au nœud source et au fur et à mesure que la traversée progresse à travers chaque nœud, ils peuvent être marqués pour être identifiés.
La traversée commence à partir d'un sommet puis se déplace vers les bords sortants. Lorsqu'une arête atteint un sommet non découvert, elle est marquée comme découverte. Mais lorsqu'une arête atteint un sommet complètement découvert ou découvert, elle est ignorée.
Pour un graphe orienté, chaque bord est visité une fois et pour le graphe non orienté, il est visité deux fois, c'est-à-dire une fois lors de la visite de chaque nœud. L'algorithme à utiliser est décidé en fonction de la façon dont les sommets découverts sont stockés. Dans l'algorithme BFS, la file d'attente est utilisée là où le sommet le plus ancien est découvert en premier, puis se propage à travers les couches à partir du sommet de départ.
Des étapes sont effectuées pour un algorithme BFS
Les étapes ci-dessous sont effectuées pour un algorithme BFS.
- Dans un graphe donné, partons d'un sommet c'est-à-dire que dans le diagramme ci-dessus c'est le noeud 0. Le niveau, dans lequel ce sommet est présent, peut être noté Couche 0.
- L'étape suivante consiste à trouver tous les autres sommets adjacents au sommet de départ, c'est-à-dire le nœud 0 ou immédiatement accessibles depuis celui-ci. Ensuite, nous pouvons marquer ces sommets adjacents comme étant présents à la couche 1.
- Il est possible d'arriver au même sommet grâce à une boucle dans le graphe. Donc, nous devons voyager uniquement vers les sommets qui devraient être présents dans la même couche.
- Ensuite, le sommet parent du sommet actuel auquel nous nous trouvons est marqué. La même chose doit être effectuée pour tous les sommets de la couche 1.
- Ensuite, l'étape suivante consiste à trouver tous ces sommets qui sont à un seul bord de tous les sommets qui se trouvent au niveau 1. Ces nouveaux ensembles de sommets seront au niveau 2.
- Le processus ci-dessus est répété jusqu'à ce que tous les nœuds soient traversés.
Exemple:
Prenons l'exemple du graphique ci-dessous et comprenons comment fonctionne l'algorithme BFS. Généralement, dans un algorithme BFS, une file d'attente est utilisée pour mettre en file d'attente les nœuds lors de leur traversée.
Dans le graphique ci-dessus, le nœud 0 doit d'abord être visité et ce nœud est mis en file d'attente dans la file d'attente ci-dessous:
Après avoir visité le nœud 0, les nœuds voisins de 0, 1 et 2 sont mis en file d'attente. La file d'attente peut être représentée comme ci-dessous: 
Ensuite, le premier nœud de la file d'attente qui est 2 sera visité. Une fois le nœud 2 visité, la file d'attente peut être représentée comme suit:
Après avoir visité le nœud 2, 5 seront mis en file d'attente et comme il n'y a pas de nœuds voisins non visités pour le nœud 5, bien que 5 soit mis en file d'attente, mais il ne sera pas visité deux fois.
Ensuite, le premier nœud de la file d'attente est 1 qui sera visité. Les nœuds voisins 3 et 4 sont mis en file d'attente. La file d'attente est représentée comme ci-dessous
Ensuite, le premier nœud de la file d'attente est 5, et pour ce nœud, il n'y a plus de nœuds voisins non visités. Il en va de même pour les nœuds 3 et 4 pour lesquels il n'y a plus de nœuds voisins non visités.
Ainsi, tous les nœuds sont traversés et enfin, la file d'attente devient vide.
Conclusion
L'algorithme de recherche de largeur présente de grands avantages pour le recommander. L'une des nombreuses applications de l'algorithme BFS est de calculer le chemin le plus court. En outre, il est utilisé dans le réseautage pour trouver des nœuds voisins et peut être trouvé dans les sites de réseautage social, la diffusion en réseau et la collecte des ordures. Les utilisateurs doivent comprendre l'exigence et le modèle de données pour l'utiliser pour de meilleures performances.
Articles recommandés
Cela a été un guide pour l'algorithme BFS. Nous discutons ici le concept, le fonctionnement, les étapes et l'exemple de performance dans l'algorithme BFS. Vous pouvez également consulter nos autres articles suggérés pour en savoir plus -
- Qu'est-ce qu'un algorithme gourmand?
- Algorithme de traçage de rayons
- Algorithme de signature numérique
- Qu'est-ce que Java Hibernate?
- Cryptographie à signature numérique
- BFS VS DFS | 6 principales différences avec l'infographie