Avantage de la première recherche en profondeur sur la largeur de la première recherche ou vice versa
J'ai étudié les deux graphique de la traversée algorithmes de parcours en profondeur d'abord de la recherche et de l'ampleur de la première recherche.Depuis les deux algorithmes sont utilisés pour résoudre le même problème de graphique de la traversée, je voudrais savoir comment choisir entre les deux.Je veux dire, c'est un plus efficace que l'autre, ou aucune raison pourquoi j'ai choisi de l'un sur l'autre dans un scénario particulier ?
Merci
source d'informationauteur Kris
Vous devez vous connecter pour publier un commentaire.
Principale différence pour moi, c'est un peu théorique. Si vous avait une infinie taille graphique puis DFS ne trouverez jamais un élément s'il existe en dehors de la première voie qu'il choisit. Elle serait essentiellement continuez à descendre le premier chemin et de ne jamais le trouver l'élément. Le BFS finirait par trouver l'élément.
Si la taille du graphe est finie, DFS trouverait probablement une des valeurs aberrantes (plus grande distance entre la racine et le but) de l'élément plus rapide là où la SECTION trouverait plus près de l'élément de plus en plus vite. Sauf dans le cas où DFS choisit le chemin de la faible profondeur de l'élément.
En général, BFS est mieux pour les problèmes liés au fait de trouver les chemins les plus courts ou un peu des problèmes connexes. Car ici, vous aller d'un nœud à nœud tous adjacentes et, par conséquent, vous pouvez effectivement déplacer à partir de la longueur de chemin d'accès à un chemin de longueur deux et ainsi de suite.
Tout DFS sur l'autre extrémité permet le plus de problèmes de connectivité et également dans la recherche de cycles dans le graphe(bien que je pense que vous pourriez être en mesure de trouver des cycles avec un peu de modification de BFS trop). Déterminer la connectivité avec DFS est trivial, si vous appelez de l'explorer procédure deux fois de la dsv de la procédure, alors le graphe est déconnecté (c'est pour un graphe non-dirigé). Vous pouvez voir la forte composante connexe de l'algorithme pour un graphe orienté ici, qui est une modification de la dsv. Une autre application de la DFS est le tri topologique.
Ces quelques applications de ces deux algorithmes:
DFS:
Connectivité
Vivement Les Composants Raccordés
Le Tri Topologique
BFS:
Plus court Chemin(Dijkstra est quoi une modification de BFS).
Tester si le graphe est Bipartitie.
Lors de la traversée d'une multipliez-graphe connexe, l'ordre dans lequel les nœuds sont parcourus peuvent influencer grandement (de plusieurs ordres de grandeur) le nombre de nœuds d'être suivis par la traversée de la méthode. Certains types d'algorithmes sera massivement mieux lors de l'utilisation de largeur tout d'abord, les autres seront massivement mieux lors de l'utilisation de la profondeur de recherche.
À l'un des extrêmes, en faisant une recherche depth-first sur un arbre binaire à N nœuds feuilles exige que la traversée de la méthode de garder une trace de lgN nœuds, tandis que une largeur tout d'abord la recherche de besoin de garder la trace d'au moins N/2 nœuds (puisque l'on peut analyser tous les autres nœuds avant qu'il analyse toutes les nœuds feuilles; immédiatement avant la numérisation de la première feuille, il aurait rencontré N/2 de l'leafs nœuds parents qui doivent être suivis séparément depuis aucun d'entre eux font référence les uns aux autres).
À l'autre extrême, en faisant un flot de remplissage sur un NxN grille avec une méthode qui, si son pixel n'a pas été coloré encore, les couleurs, que pixel et les inondations remplit ses voisins exigera replacement O(N) taille du pixel de coordonnées, à l'aide de largeur tout d'abord de recherche, mais en O(N^2) pixel de coordonnées en utilisant la profondeur de la première. Lors de l'utilisation de la largeur-première de la recherche, de la peinture semblent "s'étaler", indépendamment de la forme à peindre; lors de l'utilisation de la profondeur-premier algorithme de peindre une spirale rectangulaire, dont chaque ligne est droite sur un côté et dentelée sur les autres (les faces doivent être droites, et dont dépend l'exacte algorithme utilisé), toutes les sections droites obtiendrez peint avant tout de la déchiquetées, ce qui signifie que le système doit suivre l'emplacement de chaque jag séparément.
Complète/arbre parfait, DFS prend un linéaire de la quantité d'espace à l'égard de la profondeur de l'arbre tandis que BFS prend une exponentielle de la quantité d'espace à l'égard de la profondeur de l'arbre. C'est parce que pour BFS le nombre maximum de nœuds dans la file d'attente est proportionnelle au nombre de nœuds dans un niveau de l'arbre. DFS le nombre maximum de nœuds dans la pile est proportionnelle à la profondeur de l'arbre.
Dans certaines langues, une SECTION est un peu plus de choix
parce que la plus simple de mise en œuvre de DFS est
récursif, ce qui introduit une surcharge, et aussi
pourrait provoquer de votre code de frapper la pile de limite de taille pour les
grands graphes.
L'avantage évident (et l'application) de la SECTION est
que non pondérée de graphiques, il peut être utilisé pour construire
un plus court chemin de u à v. Cela a de nombreux
applications-par exemple, vous pouvez calculer l'
plus petit nombre de coups nécessaires pour résoudre une
puzzle en exécutant une BFS sur son espace d'état.
BFS peut même vous donner la plus courte des distances de
un sommet u à tous les autres sommets du graphe: pour chaque
vertex, rappelez-vous juste le bord qui a été utilisé pour
le découvrir.