Avant d'examiner les différences entre BFS et DFS, nous devons d'abord connaître BFS et DFS séparément.

Qu’est-ce que BFS ?

BFS représente Recherche en largeur d'abord . Il est également connu sous le nom parcours d'ordre de niveau . La structure de données Queue est utilisée pour le parcours Breadth First Search. Lorsque nous utilisons l'algorithme BFS pour le parcours dans un graphe, nous pouvons considérer n'importe quel nœud comme nœud racine.

Considérons le graphique ci-dessous pour la première traversée de recherche en largeur.

connecter la base de données Java

Supposons que nous considérions le nœud 0 comme un nœud racine. Par conséquent, le parcours commencerait à partir du nœud 0.

Une fois le nœud 0 supprimé de la file d'attente, il est imprimé et marqué comme nœud visité.

Une fois le nœud 0 supprimé de la file d'attente, les nœuds adjacents du nœud 0 seront insérés dans une file d'attente comme indiqué ci-dessous :

Le nœud 1 sera désormais supprimé de la file d'attente ; il est imprimé et marqué comme nœud visité

Une fois le nœud 1 supprimé de la file d'attente, tous les nœuds adjacents d'un nœud 1 seront ajoutés dans une file d'attente. Les nœuds adjacents du nœud 1 sont 0, 3, 2, 6 et 5. Mais nous devons insérer uniquement les nœuds non visités dans une file d'attente. Puisque les nœuds 3, 2, 6 et 5 ne sont pas visités ; par conséquent, ces nœuds seront ajoutés dans une file d'attente comme indiqué ci-dessous :

Le nœud suivant est le 3 dans une file d'attente. Ainsi, le nœud 3 sera supprimé de la file d'attente, il sera imprimé et marqué comme visité comme indiqué ci-dessous :

Une fois le nœud 3 supprimé de la file d'attente, tous les nœuds adjacents du nœud 3, à l'exception des nœuds visités, seront ajoutés dans une file d'attente. Les nœuds adjacents du nœud 3 sont 0, 1, 2 et 4. Puisque les nœuds 0, 1 sont déjà visités et que le nœud 2 est présent dans une file d'attente ; par conséquent, nous devons insérer uniquement le nœud 4 dans une file d'attente.

Language de machine

Désormais, le nœud suivant dans la file d'attente est 2. Ainsi, 2 serait supprimé de la file d'attente. Il est imprimé et marqué comme visité comme indiqué ci-dessous :

Une fois le nœud 2 supprimé de la file d'attente, tous les nœuds adjacents du nœud 2, à l'exception des nœuds visités, seront ajoutés dans une file d'attente. Les nœuds adjacents du nœud 2 sont 1, 3, 5, 6 et 4. Puisque les nœuds 1 et 3 ont déjà été visités et que 4, 5, 6 sont déjà ajoutés dans la file d'attente ; par conséquent, nous n'avons pas besoin d'insérer de nœud dans la file d'attente.

L'élément suivant est 5. Ainsi, 5 serait supprimé de la file d'attente. Il est imprimé et marqué comme visité comme indiqué ci-dessous :

Une fois le nœud 5 supprimé de la file d'attente, tous les nœuds adjacents du nœud 5, à l'exception des nœuds visités, seront ajoutés dans la file d'attente. Les nœuds adjacents du nœud 5 sont 1 et 2. Puisque les deux nœuds ont déjà été visités ; par conséquent, il n’y a aucun sommet à insérer dans une file d’attente.

Le nœud suivant est 6. Ainsi, 6 serait supprimé de la file d'attente. Il est imprimé et marqué comme visité comme indiqué ci-dessous :

Une fois le nœud 6 supprimé de la file d'attente, tous les nœuds adjacents du nœud 6, à l'exception des nœuds visités, seront ajoutés dans la file d'attente. Les nœuds adjacents du nœud 6 sont 1 et 4. Puisque le nœud 1 a déjà été visité et que le nœud 4 est déjà ajouté dans la file d'attente ; par conséquent, il n'y a pas de sommet à insérer dans la file d'attente.

L'élément suivant dans la file d'attente est 4. Ainsi, 4 serait supprimé de la file d'attente. Il est imprimé et marqué comme visité.

Une fois le nœud 4 supprimé de la file d'attente, tous les nœuds adjacents du nœud 4, à l'exception des nœuds visités, seront ajoutés dans la file d'attente. Les nœuds adjacents du nœud 4 sont 3, 2 et 6. Puisque tous les nœuds adjacents ont déjà été visités ; il n'y a donc aucun sommet à insérer dans la file d'attente.

Qu’est-ce que le DFS ?

DFS signifie Recherche en profondeur d'abord. Dans le parcours DFS, la structure de données de pile est utilisée, qui fonctionne sur le principe LIFO (Last In First Out). Dans DFS, le parcours peut être démarré à partir de n'importe quel nœud, ou nous pouvons dire que n'importe quel nœud peut être considéré comme un nœud racine jusqu'à ce que le nœud racine ne soit pas mentionné dans le problème.

mylivecricket.in

Dans le cas de BFS, l'élément qui est supprimé de la file d'attente, les nœuds adjacents du nœud supprimé sont ajoutés à la file d'attente. En revanche, dans DFS, l'élément qui est supprimé de la pile, alors un seul nœud adjacent d'un nœud supprimé est ajouté dans la pile.

Considérons le graphique ci-dessous pour le parcours Depth First Search.

Considérez le nœud 0 comme nœud racine.

Tout d’abord, nous insérons l’élément 0 dans la pile comme indiqué ci-dessous :

Le nœud 0 a deux nœuds adjacents, c'est-à-dire 1 et 3. Nous ne pouvons désormais prendre qu'un seul nœud adjacent, 1 ou 3, pour le parcours. Supposons que nous considérions le nœud 1 ; par conséquent, 1 est inséré dans une pile et est imprimé comme indiqué ci-dessous :

Nous allons maintenant examiner les sommets adjacents du nœud 1. Les sommets adjacents non visités du nœud 1 sont 3, 2, 5 et 6. Nous pouvons considérer n'importe lequel de ces quatre sommets. Supposons que nous prenons le nœud 3 et l'insérons dans la pile comme indiqué ci-dessous :

insérer un filigrane dans Word

Considérons les sommets adjacents non visités du nœud 3. Les sommets adjacents non visités du nœud 3 sont 2 et 4. Nous pouvons prendre l'un ou l'autre des sommets, c'est-à-dire 2 ou 4. Supposons que nous prenons le sommet 2 et l'insérons dans la pile comme indiqué ci-dessous :

Les sommets adjacents non visités du nœud 2 sont 5 et 4. Nous pouvons choisir l'un ou l'autre des sommets, c'est-à-dire 5 ou 4. Supposons que nous prenions le sommet 4 et que nous l'insérions dans la pile comme indiqué ci-dessous :

Nous allons maintenant considérer les sommets adjacents non visités du nœud 4. Le sommet adjacent non visité du nœud 4 est le nœud 6. Par conséquent, l'élément 6 est inséré dans la pile comme indiqué ci-dessous :

Après avoir inséré l'élément 6 dans la pile, nous examinerons les sommets adjacents non visités du nœud 6. Comme il n'y a pas de sommets adjacents non visités du nœud 6, nous ne pouvons donc pas nous déplacer au-delà du nœud 6. Dans ce cas, nous effectuerons retour en arrière . L'élément le plus haut, c'est-à-dire 6, serait retiré de la pile comme indiqué ci-dessous :

L'élément le plus haut de la pile est 4. Puisqu'il n'y a plus de sommets adjacents non visités à gauche du nœud 4 ; par conséquent, le nœud 4 est retiré de la pile comme indiqué ci-dessous :

L'élément suivant le plus haut de la pile est 2. Nous allons maintenant examiner les sommets adjacents non visités du nœud 2. Puisqu'il ne reste qu'un seul nœud non visité, c'est-à-dire 5, le nœud 5 serait donc poussé dans la pile au-dessus de 2 et serait imprimé. comme indiqué ci-dessous:

Java version Linux

Nous allons maintenant vérifier les sommets adjacents du nœud 5, qui ne sont toujours pas visités. Puisqu'il n'y a plus de sommet à visiter, nous retirons l'élément 5 de la pile comme indiqué ci-dessous :

Nous ne pouvons pas aller plus loin 5, nous devons donc effectuer un retour en arrière. En cas de retour en arrière, l'élément le plus haut serait retiré de la pile. L'élément le plus haut est 5 qui serait retiré de la pile, et nous revenons au nœud 2 comme indiqué ci-dessous :

Nous allons maintenant vérifier les sommets adjacents non visités du nœud 2. Comme il n'y a plus de sommet adjacent à visiter, nous effectuons donc un retour en arrière. Lors du retour en arrière, l'élément le plus haut, c'est-à-dire 2, serait retiré de la pile et nous revenons au nœud 3 comme indiqué ci-dessous :

Nous allons maintenant vérifier les sommets adjacents non visités du nœud 3. Comme il ne reste plus aucun sommet adjacent à visiter, nous effectuons donc un retour en arrière. Lors du retour en arrière, l'élément le plus haut, c'est-à-dire 3, serait retiré de la pile et nous reviendrions au nœud 1 comme indiqué ci-dessous :

Après avoir extrait l'élément 3, nous vérifierons les sommets adjacents non visités du nœud 1. Puisqu'il n'y a plus de sommet à visiter ; par conséquent, le retour en arrière sera effectué. Lors du retour en arrière, l'élément le plus haut, c'est-à-dire 1, serait retiré de la pile et nous reviendrions au nœud 0 comme indiqué ci-dessous :

Nous vérifierons les sommets adjacents du nœud 0, qui ne sont toujours pas visités. Comme il n’y a plus de sommet adjacent à visiter, nous effectuons donc un retour en arrière. En cela, un seul élément, c'est-à-dire 0 restant dans la pile, serait retiré de la pile comme indiqué ci-dessous :

Comme nous pouvons le constater sur la figure ci-dessus, la pile est vide. Nous devons donc arrêter le parcours DFS ici, et les éléments qui sont imprimés sont le résultat du parcours DFS.

Différences entre BFS et DFS

Voici les différences entre le BFS et le DFS :