Différence entre BFS et DFS

BFS vs DFS

La largeur de la première recherche (également appelée BFS) est une méthode de recherche utilisée pour élargir tous les nœuds d’un graphe. Il accomplit cette tâche en recherchant chaque solution afin d'examiner et de développer ces nœuds (ou une combinaison de séquences qui s'y trouvent). En tant que tel, un système BFS n'utilise pas d'algorithme heuristique (ni d'algorithme qui recherche une solution à travers plusieurs scénarios). Une fois que tous les noeuds sont obtenus, ils sont ajoutés à une file d'attente appelée Première file d'attente, Premier sorti. Les nœuds qui n'ont pas été explorés sont "stockés" dans un conteneur marqué "ouvert"; une fois explorés, ils sont transportés dans un conteneur portant la mention «fermé».

La recherche approfondie en profondeur (également connue sous le nom de DFS) est une méthode de recherche qui approfondit le nœud enfant d'une recherche jusqu'à ce qu'un objectif soit atteint (ou jusqu'à ce qu'il y ait un nœud sans autre permutation ni "enfant"). Une fois qu'un objectif est trouvé, la recherche effectue un retour sur un nœud précédent associé à une solution, en répétant le processus jusqu'à ce que tous les nœuds aient été correctement recherchés. En tant que tels, les nœuds continuent d'être mis de côté pour une exploration plus poussée - on parle de mise en œuvre non récursive..

Les caractéristiques du système de fichiers BFS sont la complexité de l'espace et du temps, son exhaustivité, la preuve de son exhaustivité et son optimalité. La complexité de l'espace fait référence à la proportion du nombre de nœuds au plus bas niveau d'une recherche. La complexité temporelle fait référence à la durée réelle utilisée pour prendre en compte chaque chemin emprunté par un nœud dans une recherche. L'intégralité est essentiellement une recherche qui trouve une solution dans un graphique, quel que soit son type. La preuve de la complétude est le niveau le moins profond auquel un objectif se trouve dans un nœud à une profondeur définie. Enfin, l’optimalité fait référence à un BFS non pondéré - c’est un graphique utilisé pour le coût unitaire.

Un DFS est la sortie la plus naturelle qui utilise un arbre recouvrant - qui est un arbre composé de tous les sommets et de certaines arêtes d’un graphe non orienté. Dans cette formation, le graphe est divisé en trois classes: arêtes avant, pointant d'un nœud vers un nœud enfant; bords arrières, pointant d'un noeud à un noeud précédent; et des bords croisés, qui ne font ni l'un ni l'autre.

Résumé:

1. Un système BFS recherche chaque solution d'un graphique pour développer ses nœuds. un DFS s'enfonce profondément dans un nœud enfant jusqu'à ce qu'un objectif soit atteint.

2. Les caractéristiques d'un système de fichiers BFS sont la complexité de l'espace et du temps, son exhaustivité, la preuve de son exhaustivité et son optimalité. la sortie la plus naturelle pour un DFS est un arbre recouvrant avec trois classes: les bords avant, les bords arrière et les bords croisés.