Différence entre BFS VS DFS
La recherche en largeur d'abord (BFS) et la recherche en profondeur en premier (DFS) sont deux algorithmes importants utilisés pour la recherche. Breadth-First Search commence sa recherche à partir du premier nœud, puis se déplace à travers les niveaux qui sont plus proches du nœud racine tandis que l'algorithme Depth First Search commence par le premier nœud, puis termine son chemin vers le nœud final du chemin respectif. Les deux algorithmes traversent chaque nœud pendant la recherche. Différents codes sont écrits pour les deux algorithmes pour exécuter le processus de traversée. Ils sont également considérés comme des algorithmes de recherche importants en intelligence artificielle.
Dans cette rubrique, nous allons en apprendre davantage sur BFS VS DFS.
Comment fonctionnent BFS et DFS?
Le mécanisme de travail des deux algorithmes est expliqué ci-dessous avec des exemples. Veuillez vous y référer pour une meilleure compréhension de l'approche utilisée.
Exemple de recherche en largeur
- Étape 1: N1 est le nœud racine, il commencera donc à partir d'ici. N1 est connecté à trois nœuds N2, N3 et N4. Les trois nœuds ne sont pas encore visités. Donc, nous partons de N2 et le stockons dans la file d'attente. Ainsi, la file d'attente nommée Q ne contient que N2.
Q: N2
- Étape 2: Ensuite, le nœud qui est connecté à N1 est N3. Puisque nous avons traversé ou visité le nœud, nous le stockerons dans la file d'attente. Ainsi, la file d'attente mise à jour est
Q: N3, N2
- Étape 3: Ensuite, le nœud qui est connecté au nœud racine est N4. Nous allons le stocker dans la file d'attente.
Q: N4, N3, N2
- Étape 4: Tous les nœuds connectés à N1 sont stockés dans la file d'attente. Maintenant, nous supprimons N2 de la file d'attente selon le principe First in First Out (FIFO) et trouvons les nœuds qui sont connectés au N2, c'est-à-dire N5. N5 n'est pas visité une seule fois, nous allons donc le stocker dans la file d'attente.
Q: N5, N4, N3
- Étape 5: Tous les sommets sont visités, nous continuons donc à supprimer les nœuds de la file d'attente jusqu'à ce qu'elle soit vide.
Profondeur Premier exemple de recherche
- Étape 1: Nous allons commencer avec N1 comme nœud de départ et le stocker dans une pile S. N1 est connecté à trois nœuds voisins N2, N3 et N4. En commençant par N2 (vous pouvez commencer par ordre alphabétique ou numérique), nous allons le mettre dans la pile.
S: N2 (haut), N1
- Étape 2: Maintenant, les nœuds voisins de N2 sont N1 et N5. Puisque N1 est déjà présent dans la pile, cela signifie qu'il est visité, nous allons donc prendre N5 et le mettre dans la pile S.
S: N5 (haut), N2, N1
- Étape 3: Maintenant, les nœuds voisins de N5 sont N3 et N4. Nous commençons le N3 et le mettons dans la pile.
S: N3 (haut), N5, N2, N1
Maintenant, N3 est connecté à N5 et N1 qui sont déjà présents dans la pile, ce qui signifie qu'ils sont visités, nous allons donc supprimer N3 de la pile selon le principe du dernier entré, premier sorti (LIFO).
S: N5 (haut), N2, N1
- Étape 4: Maintenant, nous allons mettre le dernier nœud que nous n'avons pas rencontré dans l'ensemble traversant en N4 et le mettre dans la pile.
S: N4 (haut), N5, N2, N1
- Étape 5: Maintenant, nous ne sommes pas exclus avec d'autres nœuds, nous allons donc vérifier dans la pile s'il y a des nœuds connectés aux nœuds respectifs présents qui ne sont pas visités. Si tous les nœuds connectés sont visités, nous supprimerons les nœuds présents dans la pile. Par exemple, N4 n'a pas de nœuds de connexion que nous n'avons pas vérifiés, nous allons donc le supprimer de la pile. De même, nous pouvons rechercher d'autres nœuds. L'algorithme s'arrête une fois que la pile est vide.
Comparaison directe entre BFS et DFS (infographie)
Voici les 6 principales différences entre BFS et DFS
Différences clés entre BFS et DFS
Laissez-nous discuter de certaines des principales différences entre BFS et DFS
- La recherche en largeur (BFS) commence à partir du nœud racine et visite tous les nœuds respectifs qui lui sont attachés tandis que DFS démarre à partir du nœud racine et termine le chemin d'accès complet attaché au nœud.
- BFS suit l'approche de Queue tandis que DFS suit l'approche de Stack.
- L'approche utilisée dans BFS est optimale tandis que le processus utilisé dans DFS n'est pas optimal.
- Si notre objectif est de trouver le chemin le plus court, BFS est préféré à DFS.
Tableau de comparaison BFS et DFS
Discutons de la meilleure comparaison entre BFS et DFS
| BFS | DFS |
| La forme complète de BFS est Breadth-First Search. | La forme complète de DFS est Depth First Search |
| BFS est destiné à trouver la distance la plus courte et commence à partir du premier nœud ou nœud racine et se déplace sur tous ses nœuds attachés aux nœuds respectifs. Vous pouvez obtenir une vue claire de son mécanisme de fonctionnement après avoir suivi l'exemple ci-dessous. | DFS suit une approche basée sur la profondeur et complète le chemin complet à travers tous les nœuds attachés au nœud respectif. Vous pouvez obtenir une vue claire de son mécanisme de fonctionnement après avoir suivi l'exemple ci-dessous. |
| Cela se fait en utilisant le principe Queue, qui est l'approche First In First Out (FIFO). | Cela se fait en utilisant le principe Stack, qui est l'approche Last In First Out (LIFO). |
| Les nœuds traversés plusieurs fois sont supprimés de la file d'attente. | Les nœuds visités sont insérés dans la pile et plus tard, s'il n'y a plus de nœuds à visiter, ils sont supprimés. |
| Il est relativement plus lent que la fonction Depth First Search. | Il est plus rapide que l'algorithme Breadth-First Search. |
| L'allocation de mémoire est supérieure à l'algorithme Depth First Search. | L'allocation de mémoire est comparativement inférieure à l'algorithme de recherche en largeur d'abord |
Conclusion
Il existe de nombreuses applications où les algorithmes ci-dessus sont utilisés comme apprentissage automatique ou pour trouver des solutions liées à l'intelligence artificielle, etc. Ils sont principalement utilisés dans les graphiques pour déterminer s'il est bipartite ou non, pour détecter des cycles ou des composants connectés. Ils sont également considérés comme des algorithmes importants pour trouver le chemin ou pour trouver la distance la plus courte. Selon les besoins de l'entreprise, nous pouvons utiliser deux algorithmes. Cependant, Breadth-First Search est considéré comme un moyen optimal plutôt que l'algorithme Depth First Search.
Articles recommandés
Ceci est un guide de BFS VS DFS. Ici, nous discutons des principales différences BFS VS DFS avec des infographies et un tableau de comparaison. Vous pouvez également consulter les articles suivants pour en savoir plus -
- Algorithme BFS
- TeraData vs Oracle
- Big Data vs Data Warehouse
- Big Data vs Apache Hadoop: Comparaison des 4 meilleurs que vous devez apprendre