La principale différence entre BFS et DFS est que BFS procède niveau par niveau tandis que DFS suit d’abord un chemin du nœud de départ au nœud de fin (sommet), puis un autre chemin du début à la fin, et ainsi de suite jusqu’à ce que tous les nœuds soient visités. De plus, BFS utilise la file d’attente pour stocker les nœuds tandis que DFS utilise la pile pour la traversée des nœuds.
BFS et DFS sont les méthodes de traversée utilisées dans la recherche d’un graphique. La traversée de graphe est le processus de visite de tous les nœuds du graphe. Un graphe est un groupe de sommets « V » et d’arêtes « E » se connectant aux sommets.
Contenu: BFS Vs DFS
- Comparison Chart
- Definition
- Key Differences
- Conclusion
Comparison Chart
| Basis for comparison | BFS | DFS |
|---|---|---|
| Basic | Vertex-based algorithm | Edge-based algorithm |
| Data structure used to store the nodes | Queue | Stack |
| Memory consumption | Inefficient | Efficient |
| Structure de l’arbre construit | Large et court | Étroit et long |
| Mode traversante | Les sommets non visités les plus anciens sont explorés au début. | Les sommets le long de l’arête sont explorés au début. |
| Optimalité | Optimale pour trouver la distance la plus courte, pas en coût. | Non optimal |
| L’application | Examine le graphique bipartite, la composante connectée et le chemin le plus court présents dans un graphique. | Examine le graphe connecté à deux arêtes, le graphe fortement connecté, le graphe acyclique et l’ordre topologique. |
Définition de BFS
La première recherche en largeur (BFS) est la méthode de traversée utilisée dans les graphiques. Il utilise une file d’attente pour stocker les sommets visités. Dans cette méthode, l’accent est mis sur les sommets du graphe, un sommet est d’abord sélectionné, puis il est visité et marqué. Les sommets adjacents au sommet visité sont ensuite visités et stockés dans la file d’attente de manière séquentielle.
De même, les sommets stockés sont ensuite traités un par un, et leurs sommets adjacents sont visités. Un nœud est entièrement exploré avant de visiter tout autre nœud du graphique, en d’autres termes, il traverse d’abord les nœuds les moins profonds inexplorés.
Exemple
Nous avons un graphe dont les sommets sont A, B, C, D, E, F, G. En considérant A comme point de départ. Les étapes impliquées dans le processus sont les suivantes:
- Le sommet A est développé et stocké dans la file d’attente.
- Les sommets B, D et G successeurs de A, sont développés et stockés dans la file d’attente pendant que le sommet A est supprimé.
- Maintenant, B à l’extrémité avant de la file d’attente est supprimé avec le stockage de ses sommets successeurs E et F.
- Le sommet D se trouve à l’extrémité avant de la file d’attente est supprimé et son nœud connecté F est déjà visité.
- Le sommet G est supprimé de la file d’attente, et il a le successeur E qui est déjà visité.
- Maintenant E et F sont supprimés de la file d’attente, et son sommet successeur C est parcouru et stocké dans la file d’attente.
- Enfin C est également supprimé et la file d’attente est vide, ce qui signifie que nous avons terminé.
- La sortie générée est – A, B, D, G, E, F, C.
Applications
BFS peut être utile pour déterminer si le graphique a des composants connectés ou non. Et il peut également être utilisé pour détecter un graphique bipartite.
Un graphe est bipartite lorsque les sommets du graphe sont séparés en deux ensembles disjoints ; il n’y a pas deux sommets adjacents dans le même ensemble. Une autre méthode de vérification d’un graphique bipartite consiste à vérifier l’occurrence d’un cycle impair dans le graphique. Un graphe bipartite ne doit pas contenir de cycle impair.
BFS est également mieux à trouver le chemin le plus court dans le graphique pourrait être considéré comme un réseau.
Définition de la méthode de traversée DFS
La première recherche en profondeur (DFS) utilise la pile pour stocker les sommets visités. DFS est la méthode basée sur les arêtes et fonctionne de manière récursive où les sommets sont explorés le long d’un chemin (arête). L’exploration d’un nœud est suspendue dès qu’un autre nœud inexploré est trouvé et que les nœuds inexplorés les plus profonds sont parcourus en premier. DFS traverse / visite chaque sommet exactement une fois et chaque arête est inspectée exactement deux fois.
Exemple
Similaire à BFS permet de prendre le même graphique pour effectuer des opérations DFS, et les étapes impliquées sont:
- Considérant A comme sommet de départ qui est exploré et stocké dans la pile.
- B le sommet successeur de A est stocké dans la pile.
- Le sommet B a deux successeurs E et F, parmi eux par ordre alphabétique, E est exploré en premier et stocké dans la pile.
- Le successeur du sommet E, c’est-à-dire G est stocké dans la pile.
- Le sommet G a deux sommets connectés, et les deux sont déjà visités, donc G est sorti de la pile.
- De même, E s a également été supprimé.
- Maintenant, le sommet B est en haut de la pile, son autre nœud (sommet) F est exploré et stocké dans la pile.
- Le sommet F a deux successeurs C et D, entre eux C est traversé en premier et stocké dans la pile.
- Le sommet C n’a qu’un seul prédécesseur déjà visité, il est donc supprimé de la pile.
- Maintenant, le sommet D connecté à F est visité et stocké dans la pile.
- Comme le sommet D n’a pas de nœuds non visités, D est donc supprimé.
- De même, F, B et A sont également surgis.
- La sortie générée est – A, B, E, G, F, C, D.
Application
Les applications de DFS comprennent l’inspection du graphe connecté à deux bords, du graphe fortement connecté, du graphe acyclique et de l’ordre topologique.
Un graphe est appelé deux arêtes connectées si et seulement s’il reste connecté même si l’une de ses arêtes est supprimée. Cette application est très utile, dans les réseaux informatiques où la défaillance d’une liaison dans le réseau n’affectera pas le réseau restant, et il serait toujours connecté.
Un graphe fortement connecté est un graphe dans lequel il doit exister un chemin entre une paire ordonnée de sommets. DFS est utilisé dans le graphe dirigé pour rechercher le chemin entre chaque paire ordonnée de sommets. DFS peut facilement résoudre les problèmes de connectivité.
Différences clés Entre BFS et DFS
- BFS est un algorithme basé sur les sommets tandis que DFS est un algorithme basé sur les arêtes.
- La structure de données de file d’attente est utilisée dans BFS. D’autre part, DFS utilise la pile ou la récursivité.
- L’espace mémoire est utilisé efficacement dans DFS tandis que l’utilisation de l’espace dans BFS n’est pas efficace.
- BFS est l’algorithme optimal alors que DFS n’est pas optimal.
- DFS construit des arbres étroits et longs. Par contre, BFS construit un arbre large et court.
Conclusion
BFS et DFS, les deux techniques de recherche de graphes ont un temps d’exécution similaire mais une consommation d’espace différente, DFS prend de l’espace linéaire car nous devons nous souvenir d’un chemin unique avec des nœuds inexplorés, tandis que BFS garde chaque nœud en mémoire.
DFS donne des solutions plus profondes et n’est pas optimal, mais cela fonctionne bien lorsque la solution est dense alors que BFS est optimal, ce qui recherche d’abord l’objectif optimal.