Structure des données: DFS vs BFS?
si on nous donne un problème de graphique, Comment savoir si nous devons utiliser l'algorithme bfs ou dfs??? ou quand utilise-t-on l'algorithme dfs ou l'algorithme bfs. Quelles sont les différences et les avantages de l'un sur l'autre?
5 réponses
BFS va utiliser plus de mémoire en fonction du facteur de branchement... cependant, BFS est un algorithme complet... ce qui signifie que si vous l'utilisez pour chercher quelque chose dans la profondeur la plus basse possible, BFS vous donnera la solution optimale.
BFS l'espace de la complexité est O(b^d)... le facteur de branchement élevé à la profondeur (peut être BEAUCOUP de mémoire).
DFS d'autre part, est beaucoup mieux au sujet de l'espace cependant il peut trouver une solution sous-optimale. Ce qui signifie, si vous êtes juste à la recherche d'un chemin d'un sommet à l'autre, vous pouvez trouver la solution sous-optimale (et vous arrêter là) avant de trouver le chemin le plus court. DFS espace complexité est O(|V|)... ce qui signifie que le plus de mémoire qu'il peut prendre est le plus long chemin possible.
ils ont la même complexité temporelle.
en termes de mise en oeuvre, BFS est habituellement implémentée avec Queue, alors que la DFS utilise un Stack.
largeur cherche d'abord les frères et sœurs. la profondeur d'abord cherche évidemment les enfants d'abord. Donc, je suppose que ça dépend du genre de recherche que vous cherchez à faire. les recherches de types de relations entre les champs se prêteraient probablement à bfs, où les recherches hiérarchiques (arbres, dossiers, rangs, etc.) seraient plus appropriées en tant que dfs.
les deux traversées du graphe promettent une chose: une traversée complète du graphe, en visitant chaque sommet du graphe. Si vous n'avez pas de contraintes de mémoire, DFS est un bon choix, car BFS prend beaucoup d'espace. Donc, le choix entre ces deux options dépend de vos besoins.
vous voulez trouver les composants (fortement/) connectés du graphique? ou résoudre le labyrinthe ou sudoku? Utilisez DFS. Si vous regardez attentivement, les pré-ordre, Post-ordre et dans l'ordre sont toutes des variantes de la DFS. Donc, oui, ce sont des applications intéressantes.
BFS si vous voulez tester si un graphe est bipartite, trouvez le chemin le plus court entre deux noeuds ou applications qui nécessitent de telles tâches.
dans la file d'attente bfs est utilisé tandis que dans la pile dfs est utilisé pour stocker les vertices selon graph traversal.
2-dans le processus bfs est fait niveau à niveau (selon dirigé ou non dirigé graphique)
alors que dans dfs le processus est fait en profondeur (le processus de première visite du noeud racine et un autre est fait loin et ensuite appliquer rétrotracking du dernier noeud au noeud racine).
BFS est extrêmement bon pour les chemins Les plus courts tandis que DFS ne l'est pas.