Les différence principale entre BFS et DFS est que BFS ou Breadth First Search procède niveau après niveau tandis que DFS ou Depth First Search suit un chemin du début au nœud de fin, puis passe à l'autre chemin du début à la fin et ainsi de suite, jusqu'à visiter tous les nœuds.

Un graphique est une structure de données non linéaire qui organise les éléments de données en tant que modèle de réseau. Les nœuds d'un graphe sont appelés sommets et les arêtes relient ces nœuds. Il est possible de résoudre la plupart des problèmes de graphes en utilisant des méthodes de recherche. La recherche en largeur d'abord (BFS) et la recherche en profondeur d'abord (DFS) sont des méthodes de recherche couramment utilisées. En bref, BFS utilise une file d'attente tandis que DFS utilise une pile.

BFS, DFS

Qu'est-ce que BFS

BFS signifie Recherche souffle d'abord. Il utilise une file d'attente. Le processus est le suivant.

Un exemple est le suivant.

Figure 1: BFS

Supposons que le sommet de départ dans l'image ci-dessus soit 1. Les nœuds connectés à 1 sont 2 et 4. Nous pouvons donc placer 1, 2 et 4 dans une file d'attente. La sortie est 1, 2, 4. Pour 1, il n'y a plus de sommets. Par conséquent, nous pouvons supprimer 1 de la file d'attente. Nous pouvons maintenant passer à 2. Les sommets adjacents de 2 sont 3, 5 et 6. Ainsi, nous pouvons placer 3, 5 et 6 dans la file d'attente. La sortie est 1, 2, 4, 3, 6. En plus de ces trois nombres, il n'y a pas de sommets adjacents connectés à 2. Ainsi, nous pouvons supprimer 2 de la file d'attente. Passons maintenant à 4. Le seul nœud adjacent à 4 est 6. Il a déjà été visité. Il n'y a plus de sommets pour 4. Par conséquent, nous pouvons retirer 4 de la file d'attente. Vous devez répéter ce processus jusqu'à ce que la file d'attente soit vide. Il indique la fin de l'opération de recherche.

Qu'est-ce que DFS

DFS signifie Recherche en profondeur d'abord. Le processus est le suivant.

Visitez le sommet adjacent non visité et marquez-le comme visité. Ensuite, affichez-le en sortie et poussez-le dans la pile.

Si aucun sommet adjacent n'est trouvé, faites apparaître le sommet de la pile.

Continuez avec les deux étapes ci-dessus jusqu'à ce que la pile soit vide.

Figure 2: SFN

Le sommet de départ est A. Il est poussé dans la pile. Les sommets adjacents sont B et E. Considérons B. Nous pouvons pousser B vers la pile. Comme il n'y a pas de nœuds adjacents à B, nous pouvons sortir B de la pile. La sortie est A B. Le nœud adjacent restant à A est E, nous pouvons donc ajouter E à la pile. Maintenant, la sortie est A B E.

Comme il n'y a pas de nœuds adjacents à A, nous pouvons retirer « A » de la pile. Les nœuds adjacents pour E sont C et H. Considérons maintenant C. Nous pouvons pousser C vers la pile. La sortie est A B E C. Le processus se poursuit jusqu'à ce que la pile soit vide. Il termine l'opération de recherche.

Différence entre BFS et DFS

Définition

BFS (Breadth first search) est un algorithme de parcours de graphe qui commence à parcourir le graphe à partir du nœud racine et explore tous les nœuds voisins. DFS (Depth first search) est un algorithme qui commence par le nœud initial du graphe, puis va de plus en plus profondément jusqu'à trouver le nœud requis ou le nœud qui n'a pas d'enfant. C'est donc la principale différence entre BFS et DFS.

Forme longue

Alors que BFS signifie Breadth First Search, DFS signifie Depth First Search.

Méthode de stockage des nœuds

Une autre différence majeure entre BFS et DFS est que BFS utilise la file d'attente tandis que DFS utilise la pile.

Consommation de mémoire

Méthode de traversée

La méthode de traversée est une autre différence entre BFS et DFS. BFS se concentre d'abord sur la visite des sommets non visités les plus anciens, tandis que DFS se concentre sur la visite des sommets le long du bord au début.

Conclusion

BFS et DFS sont deux méthodes de recherche pour trouver un élément dans un graphique. le différence principale entre BFS et DFS est que BFS procède niveau après niveau tandis que DFS suit un chemin du début au nœud de fin, puis passe à l'autre chemin du début à la fin et ainsi de suite jusqu'à visiter tous les nœuds.

Référence:

1. Algorithme de recherche en largeur en premier | Pseudo-code | Introduction, Education 4u, 22 mars 2018, disponible ici.2. Recherche en largeur d'abord | Exemples BFS |, Education 4u, 22 mars 2018, disponible ici.3. Algorithme de recherche de profondeur d'abord | Graph Traversal Algorithm |, Education 4u, 22 mars 2018, disponible ici.4. "Algorithme BFS - Javatpoint." Www.javatpoint.com, disponible ici.5. "Algorithme DFS - Javatpoint." Www.javatpoint.com, disponible ici.