BFS vs DFS – Différence entre eux
Différence clé entre BFS et DFS
- BFS trouve le chemin le plus court vers la destination, tandis que DFS va au bas d'un sous-arbre, puis revient en arrière.
- La forme complète de BFS est la recherche en largeur d'abord, tandis que la forme complète de DFS est la recherche en profondeur.
- BFS utilise une file d'attente pour suivre le prochain emplacement à visiter. tandis que DFS utilise une pile pour garder une trace du prochain emplacement à visiter.
- BFS traverse en fonction du niveau de l'arborescence, tandis que DFS traverse en fonction de la profondeur de l'arborescence.
- BFS est implémenté à l'aide d'une liste FIFO ; d'autre part, DFS est implémenté à l'aide d'une liste LIFO.
- Dans BFS, vous ne pouvez jamais être piégé dans des boucles finies, alors que dans DFS, vous pouvez être piégé dans des boucles infinies.
Qu'est-ce que BFS ?
BFS est un algorithme utilisé pour représenter graphiquement des données, rechercher des arbres ou traverser des structures. L'algorithme visite et marque efficacement tous les nœuds clés d'un graphique de manière précise dans le sens de l'étendue.
Cet algorithme sélectionne un seul nœud (point initial ou source) dans un graphe puis visite tous les nœuds adjacents au nœud sélectionné. Une fois que l'algorithme visite et marque le nœud de départ, il se déplace vers les nœuds non visités les plus proches et les analyse.
Une fois visités, tous les nœuds sont marqués. Ces itérations se poursuivent jusqu'à ce que tous les nœuds du graphe aient été visités et marqués avec succès. La forme complète de BFS est la recherche en largeur d'abord.
Qu'est-ce que le SDF ?
DFS est un algorithme permettant de rechercher ou de parcourir des graphiques ou des arbres dans le sens de la profondeur. L'exécution de l'algorithme commence au nœud racine et explore chaque branche avant de revenir en arrière. Il utilise une structure de données de pile pour se souvenir, pour obtenir le sommet suivant et pour lancer une recherche, chaque fois qu'une impasse apparaît dans une itération. La forme complète de DFS est la recherche en profondeur.
Différence entre l'arbre binaire BFS et DFS
Voici les différences importantes entre BFS et DFS.
BFS | DFS |
---|---|
BFS trouve le chemin le plus court vers la destination. | DFS va au bas d'un sous-arbre, puis revient en arrière. |
La forme complète de BFS est la recherche en largeur. | La forme complète de DFS est Depth First Search. |
Il utilise une file d’attente pour suivre le prochain endroit à visiter. | Il utilise une pile pour garder une trace du prochain emplacement à visiter. |
BFS traverse selon le niveau de l'arborescence. | DFS traverse en fonction de la profondeur de l'arbre. |
Il est implémenté à l'aide de la liste FIFO. | Il est implémenté à l'aide de la liste LIFO. |
Il nécessite plus de mémoire que DFS. | Il nécessite moins de mémoire que BFS. |
Cet algorithme donne la solution du chemin le moins profond. | Cet algorithme ne garantit pas la solution du chemin le moins profond. |
Il n’est pas nécessaire de revenir en arrière dans BFS. | Il est nécessaire de faire marche arrière dans le DFS. |
Vous ne pouvez jamais être piégé dans des boucles finies. | Vous pouvez être piégé dans des boucles infinies. |
Si vous ne trouvez aucun objectif, vous devrez peut-être développer de nombreux nœuds avant de trouver la solution. | Si vous ne trouvez aucun objectif, un retour en arrière du nœud feuille peut se produire. |
Exemple de BFS
Dans l’exemple suivant de BFS, nous avons utilisé un graphe à 6 sommets.
Exemple de BFS
Étape 1)
Vous avez un graphique de sept nombres allant de 0 à 6.
Étape 2)
0 ou zéro a été marqué comme nœud racine.
Étape 3)
0 est visité, marqué et inséré dans la structure de données de la file d'attente.
Étape 4)
Les 0 nœuds adjacents et non visités restants sont visités, marqués et insérés dans la file d'attente.
Étape 5)
Les itérations de parcours sont répétées jusqu'à ce que tous les nœuds soient visités.
Exemple de DFS
Dans l'exemple suivant de DFS, nous avons utilisé un graphe non orienté ayant 5 sommets.
Étape 1)
Nous sommes partis du sommet 0. L'algorithme commence par le mettre dans la liste visitée et met simultanément tous ses sommets adjacents dans la Structure de données appelé pile.
Étape 2)
Vous visiterez l’élément qui se trouve en haut de la pile, par exemple 1 et accéderez à ses nœuds adjacents. C'est parce que 0 a déjà été visité. Nous visitons donc le sommet 2.
Étape 3)
Le sommet 2 a un sommet proche non visité dans 4. Par conséquent, nous l'ajoutons dans la pile et le visitons.
Étape 4)
Enfin, nous visiterons le dernier sommet 3, il ne possède aucun nœud attenant non visité. Nous avons terminé le parcours du graphique en utilisant l'algorithme DFS.
Applications du BFS
Voici les applications de BFS :
Graphiques non pondérés
L'algorithme BFS peut facilement créer le chemin le plus court et un arbre couvrant minimum pour visiter tous les sommets du graphique dans les plus brefs délais avec une grande précision.
Réseaux P2P
BFS peut être implémenté pour localiser tous les nœuds les plus proches ou voisins dans un réseau peer to peer. Cela permettra de trouver les données requises plus rapidement.
Robots d'exploration Web
Les moteurs de recherche ou les robots d'exploration Web peuvent facilement créer plusieurs niveaux d'index en utilisant BFS. L'implémentation de BFS commence à partir de la source, qui est la page Web, puis visite tous les liens de cette source.
Diffusion en réseau
Un paquet diffusé est guidé par l'algorithme BFS pour trouver et atteindre tous les nœuds pour lesquels il possède l'adresse.
Applications du DFS
Voici les applications importantes de DFS :
Graphique pondéré
Dans un graphe pondéré, le parcours du graphe DFS génère l'arbre de chemin le plus court et l'arbre couvrant minimum.
Détection d'un cycle dans un graphique
Un graphique a un cycle si nous trouvons un bord arrière pendant DFS. Par conséquent, nous devrions exécuter DFS pour le graphique et vérifier les bords arrière.
Trouver son chemin
Nous pouvons nous spécialiser dans l'algorithme DFS pour rechercher un chemin entre deux sommets.
Tri topologique
Il est principalement utilisé pour planifier des tâches à partir des dépendances données parmi le groupe de tâches. En informatique, il est utilisé dans la planification des instructions, la sérialisation des données, la synthèse logique, la détermination de l'ordre des tâches de compilation.
Recherche de composants fortement connectés d'un graphique
Il est utilisé dans le graphique DFS lorsqu'il existe un chemin entre chaque sommet du graphique et les autres sommets restants.
Résoudre des énigmes avec une seule solution
L'algorithme DFS peut être facilement adapté pour rechercher toutes les solutions d'un labyrinthe en incluant les nœuds sur le chemin existant dans l'ensemble visité.