Je comprends les différences entre DFS et BFS, mais je suis intéressé de savoir quand il est plus pratique d'utiliser l'un sur l'autre?

Quelqu'un pourrait-il donner des exemples de la façon dont DFS l'emporterait sur BFS et vice versa?

Cela dépend fortement de la structure de l'arborescence de recherche et du nombre et de l'emplacement des solutions (également appelés éléments recherchés).

• Si vous savez qu'une solution n'est pas loin de la racine de l'arbre, une première recherche en largeur (BFS) pourrait être meilleure.

• Si l'arborescence est très profonde et que les solutions sont rares, la recherche en profondeur en premier (DFS) peut prendre un temps extrêmement long, mais BFS peut être plus rapide.

• Si l'arborescence est très large, un BFS peut avoir besoin de trop de mémoire, ce qui peut donc être complètement impossible.

• Si les solutions sont fréquentes mais situées au plus profond de l'arbre, BFS pourrait ne pas être pratique.

• Si l'arborescence de recherche est très profonde, vous devrez de toute façon restreindre la profondeur de recherche pour la recherche en profondeur (DFS) (par exemple avec l'approfondissement itératif).

Mais ce ne sont que des règles de base; vous aurez probablement besoin d'expérimenter.

Recherche en profondeur

Les recherches en profondeur d'abord sont souvent utilisées dans des simulations de jeux (et des situations de type jeu dans le monde réel). Dans un jeu typique, vous pouvez choisir l'une des actions possibles. Chaque choix mène à d'autres choix, chacun conduit à d'autres choix, et ainsi de suite dans un graphique en forme d'arbre toujours croissant de possibilités.

Par exemple, dans des jeux comme les échecs, le tic-tac-toe lorsque vous décidez quel mouvement effectuer, vous pouvez imaginer mentalement un mouvement, puis les réponses possibles de votre adversaire, puis vos réponses, etc. Vous pouvez décider quoi faire en voyant quel mouvement conduit au meilleur résultat.

Seuls quelques chemins dans un arbre de jeu mènent à votre victoire. Certains mènent à une victoire de votre adversaire, lorsque vous atteignez une telle fin, vous devez sauvegarder ou revenir en arrière vers un nœud précédent et essayer un chemin différent. De cette façon, vous explorez l'arbre jusqu'à ce que vous trouviez un chemin avec une conclusion réussie. Ensuite, vous faites le premier pas sur ce chemin.

Recherche en priorité

La recherche en largeur a une propriété intéressante: elle trouve d'abord tous les sommets à une arête du point de départ, puis tous les sommets à deux arêtes, et ainsi de suite. Ceci est utile si vous essayez de trouver le chemin le plus court entre le sommet de départ et un sommet donné. Vous démarrez un BFS, et lorsque vous trouvez le sommet spécifié, vous savez que le chemin que vous avez tracé jusqu'à présent est le chemin le plus court vers le nœud. S'il y avait un chemin plus court, le BFS l'aurait déjà trouvé.

La recherche en largeur peut être utilisée pour trouver les nœuds voisins dans des réseaux peer to peer comme BitTorrent, des systèmes GPS pour trouver des emplacements à proximité, des sites de réseaux sociaux pour trouver des personnes à la distance spécifiée et des choses comme ça.

Belle explication de http://www.programmerinterview.com/index.php/data-structures/dfs-vs-bfs/

Un exemple de BFS

Voici un exemple de ce à quoi ressemblerait un BFS. C'est quelque chose comme Level Order Tree Traversal où nous utiliserons QUEUE avec l'approche ITERATIVE (la plupart du temps, RECURSION se terminera avec DFS). Les nombres représentent l'ordre dans lequel les nœuds sont accessibles dans un BFS:

Dans une première recherche approfondie, vous commencez à la racine et suivez autant que possible l'une des branches de l'arbre jusqu'à ce que le nœud que vous recherchez soit trouvé ou que vous atteigniez un nœud feuille (un nœud sans enfants). Si vous frappez un nœud feuille, vous poursuivez la recherche sur l'ancêtre le plus proche avec des enfants inexplorés.

Un exemple de DFS

Voici un exemple de ce à quoi ressemblerait un DFS. Je pense que la traversée de la commande dans l'arbre binaire commencera le travail à partir du niveau Feuille en premier. Les nombres représentent l'ordre dans lequel les nœuds sont accessibles dans un DFS:

Différences entre DFS et BFS

En comparant BFS et DFS, le grand avantage de DFS est qu'il a des besoins en mémoire beaucoup plus faibles que BFS, car il n'est pas nécessaire de stocker tous les pointeurs enfants à chaque niveau. Selon les données et ce que vous recherchez, DFS ou BFS peuvent être avantageux.

Par exemple, étant donné un arbre généalogique si l'on cherchait quelqu'un sur l'arbre qui est encore en vie, il serait prudent de supposer que cette personne serait au bas de l'arbre. Cela signifie qu'un BFS mettrait très longtemps à atteindre ce dernier niveau. Un DFS, cependant, trouverait le but plus rapidement. Mais, si quelqu'un cherchait un membre de sa famille décédé il y a très longtemps, cette personne serait plus proche du sommet de l'arbre. Ensuite, un BFS serait généralement plus rapide qu'un DFS. Ainsi, les avantages de l'une ou l'autre varient en fonction des données et de ce que vous recherchez.

Un autre exemple est Facebook; Suggestion sur Friends of Friends. Nous avons besoin d'amis immédiats pour suggérer où nous pouvons utiliser BFS. Peut-être trouver le chemin le plus court ou détecter le cycle (en utilisant la récursivité), nous pouvons utiliser DFS.

La recherche en largeur d'abord est généralement la meilleure approche lorsque la profondeur de l'arborescence peut varier, et il vous suffit de rechercher une partie de l'arborescence pour trouver une solution. Par exemple, trouver le chemin le plus court d'une valeur de départ à une valeur finale est un bon endroit pour utiliser BFS.

Depth First Search est couramment utilisé lorsque vous devez rechercher dans l’arbre entier. Il est plus facile à implémenter (à l'aide de la récursivité) que BFS, et nécessite moins d'état: alors que BFS nécessite que vous stockiez l'intégralité de la `` frontière '', DFS vous oblige uniquement à stocker la liste des nœuds parents de l'élément actuel.

DFS est plus économe en espace que BFS, mais peut aller à des profondeurs inutiles.

Leurs noms sont révélateurs: s'il y a une grande largeur (c'est-à-dire un grand facteur de branchement), mais une profondeur très limitée (par exemple, un nombre limité de "mouvements"), alors DFS peut être plus préférable à BFS.

Sur IDDFS

Il convient de mentionner qu'il existe une variante moins connue qui combine l'efficacité spatiale de DFS, mais (en résumé) la visite d'ordre de niveau de BFS, est la recherche itérative d'approfondissement en profondeur en premier . Cet algorithme revisite certains nœuds, mais il ne contribue qu'à un facteur constant de différence asymptotique.

Lorsque vous abordez cette question en tant que programmeur, un facteur se démarque: si vous utilisez la récursivité, la recherche en profondeur d'abord est plus simple à implémenter, car vous n'avez pas besoin de maintenir une structure de données supplémentaire contenant les nœuds à explorer.

Voici une recherche approfondie d'un graphique non orienté si vous stockez des informations «déjà visitées» dans les nœuds:

def dfs(origin):                               # DFS from origin:
    origin.visited = True                      # Mark the origin as visited
    for neighbor in origin.neighbors:          # Loop over the neighbors
        if not neighbor.visited: dfs(next)     # Visit each neighbor if not already visited

Si vous stockez des informations «déjà visitées» dans une structure de données distincte:

def dfs(node, visited):                        # DFS from origin, with already-visited set:
    visited.add(node)                          # Mark the origin as visited
    for neighbor in node.neighbors:            # Loop over the neighbors
        if not neighbor in visited:            # If the neighbor hasn't been visited yet,
            dfs(node, visited)                 # then visit the neighbor
dfs(origin, set())

Comparez cela à une recherche en profondeur où vous devez conserver une structure de données distincte pour la liste des nœuds à visiter, quoi qu'il arrive.

Un avantage important de BFS serait qu'il peut être utilisé pour trouver le chemin le plus court entre deux nœuds dans un graphe non pondéré. Alors que nous ne pouvons pas utiliser DFS pour la même chose .

Pour BFS, nous pouvons considérer l'exemple de Facebook. Nous recevons des suggestions pour ajouter des amis du profil FB à partir d'autres profils d'amis. Supposons que A-> B, tandis que B-> E et B-> F, ainsi A obtiendra une suggestion pour E et F. Ils doivent utiliser BFS pour lire jusqu'au deuxième niveau. DFS est plus basé sur des scénarios où nous voulons prévoir quelque chose en fonction des données que nous avons de la source à la destination. Comme déjà mentionné sur les échecs ou le sudoku. Une fois que j'ai quelque chose de différent, je pense que DFS devrait être utilisé pour le chemin le plus court, car DFS couvrira tout le chemin d'abord, puis nous pourrons décider du meilleur. Mais comme BFS utilisera l'approche gourmande, il se peut que cela ressemble à son chemin le plus court, mais le résultat final peut différer. Faites-moi savoir si ma compréhension est fausse.

Certains algorithmes dépendent de propriétés particulières de DFS (ou BFS) pour fonctionner. Par exemple, l'algorithme Hopcroft et Tarjan pour trouver des composants connectés 2 tire parti du fait que chaque nœud déjà visité rencontré par DFS est sur le chemin de la racine au nœud actuellement exploré.

Ce qui suit est une réponse complète à ce que vous demandez.

En termes simples:

L'algorithme Breadth First Search (BFS), à partir de son nom "Breadth", découvre tous les voisins d'un nœud à travers les bords extérieurs du nœud, puis il découvre les voisins non visités des voisins mentionnés précédemment à travers leurs bords extérieurs et ainsi de suite, jusqu'à ce que tous les nœuds accessibles depuis la source d'origine sont visités (nous pouvons continuer et prendre une autre source d'origine s'il reste des nœuds non visités, etc.). C'est pourquoi il peut être utilisé pour trouver le chemin le plus court (s'il y en a) d'un nœud (source d'origine) à un autre nœud si les poids des bords sont uniformes.

L'algorithme DFS (Depth First Search), à partir de son nom "Depth", découvre les voisins non visités du nœud x le plus récemment découvert à travers ses bords extérieurs. S'il n'y a pas de voisin non visité depuis le nœud x, l'algorithme revient en arrière pour découvrir les voisins non visités du nœud (à travers ses bords extérieurs) à partir desquels le nœud x a été découvert, et ainsi de suite, jusqu'à ce que tous les nœuds accessibles depuis la source d'origine soient visités. (nous pouvons continuer et prendre une autre source d'origine s'il reste des nœuds non visités, etc.).

BFS et DFS peuvent être incomplets. Par exemple, si le facteur de branchement d'un nœud est infini, ou très grand pour les ressources (mémoire) à prendre en charge (par exemple lors du stockage des nœuds à découvrir ensuite), alors BFS n'est pas complet même si la clé recherchée peut être à distance de quelques bords de la source d'origine. Ce facteur de branchement infini peut être dû à des choix infinis (nœuds voisins) d'un nœud donné à découvrir. Si la profondeur est infinie, ou très grande pour les ressources (mémoire) à prendre en charge (par exemple lors du stockage des nœuds à découvrir ensuite), alors DFS n'est pas complet même si la clé recherchée peut être le troisième voisin de la source d'origine. Cette profondeur infinie peut être due à une situation où il y a, pour chaque nœud que l'algorithme découvre, au moins un nouveau choix (nœud voisin) qui n'a pas été visité auparavant.

Par conséquent, nous pouvons conclure quand utiliser le BFS et le DFS. Supposons que nous ayons affaire à un facteur de ramification limité gérable et à une profondeur limitée gérable. Si le nœud recherché est peu profond, c'est-à-dire accessible après certains bords de la source d'origine, il est préférable d'utiliser BFS. D'un autre côté, si le nœud recherché est profond, c'est-à-dire accessible après de nombreux bords depuis la source d'origine, il est préférable d'utiliser DFS.

Par exemple, dans un réseau social, si nous voulons rechercher des personnes qui ont des intérêts similaires pour une personne spécifique, nous pouvons appliquer le BFS de cette personne comme source d'origine, car la plupart du temps ces personnes seront ses amis directs ou amis d'amis, c'est-à-dire un ou deux bords loin. D'un autre côté, si nous voulons rechercher des personnes qui ont des intérêts complètement différents d'une personne spécifique, nous pouvons appliquer le DFS de cette personne comme source d'origine, car la plupart du temps ces personnes seront très loin de lui, c'est-à-dire ami d'ami d'ami .... c'est à dire trop de bords loin.

Les applications de BFS et DFS peuvent également varier en raison du mécanisme de recherche dans chacune d'elles. Par exemple, nous pouvons utiliser BFS (en supposant que le facteur de branchement est gérable) ou DFS (en supposant que la profondeur est gérable) lorsque nous voulons simplement vérifier l'accessibilité d'un nœud à un autre sans aucune information sur l'endroit où ce nœud peut être. Les deux peuvent également résoudre les mêmes tâches comme le tri topologique d'un graphique (si c'est le cas). BFS peut être utilisé pour trouver le chemin le plus court, avec des bords de poids unitaire, d'un nœud (source d'origine) à un autre. Considérant que, DFS peut être utilisé pour épuiser tous les choix en raison de sa nature d'aller en profondeur, comme découvrir le chemin le plus long entre deux nœuds dans un graphique acyclique. DFS peut également être utilisé pour la détection de cycle dans un graphique.

En fin de compte, si nous avons une profondeur et un facteur de ramification infinis, nous pouvons utiliser la recherche d'approfondissement itératif (IDS).

Selon les propriétés de DFS et BFS. Par exemple, lorsque nous voulons trouver le chemin le plus court. nous utilisons généralement bfs, il peut garantir le «plus court». mais dfs seulement peut garantir que nous pouvons venir de ce point peut atteindre ce point, ne peut pas garantir le «plus court».

Je pense que cela dépend des problèmes que vous rencontrez.

1. chemin le plus court sur un graphe simple -> bfs
2. tous les résultats possibles -> dfs
3. recherche sur le graphique (traiter l'arbre, martix aussi comme un graphique) -> dfs ....

Étant donné que les recherches en profondeur d'abord utilisent une pile lors du traitement des nœuds, le retour en arrière est fourni avec DFS. Étant donné que les recherches de largeur en premier utilisent une file d'attente, et non une pile, pour garder une trace des nœuds traités, le retour en arrière n'est pas fourni avec BFS.

Lorsque la largeur de l'arbre est très grande et que la profondeur est faible, utilisez DFS car la pile de récursivité ne débordera pas. Utilisez BFS lorsque la largeur est faible et la profondeur est très grande pour traverser l'arbre.

C'est un bon exemple pour démontrer que BFS est meilleur que DFS dans certains cas. https://leetcode.com/problems/01-matrix/

Lorsqu'elles sont correctement implémentées, les deux solutions doivent visiter les cellules dont la distance est plus grande que la cellule actuelle +1. Mais DFS est inefficace et a visité à plusieurs reprises la même cellule résultant de la complexité O (n * n).

Par exemple,

1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
1,1,1,1,1,1,1,1, 
0,0,0,0,0,0,0,0,

Cela dépend de la situation dans laquelle il est utilisé. Chaque fois que nous avons un problème de traversée d'un graphe, nous le faisons dans un but précis. Lorsqu'il y a un problème pour trouver le chemin le plus court dans un graphe non pondéré, ou pour savoir si un graphe est bipartite, nous pouvons utiliser BFS. Pour les problèmes de détection de cycle ou toute logique nécessitant un retour en arrière, nous pouvons utiliser DFS.