|
? Une profondeur d'abord est un algorithme qui recherche la procédure un graphique ou une structure arborescente en se rendant aussi loin dans l'arbre comme il peut avant de reculer. L' exécution de l'algorithme nécessaire pour terminer dépend du nombre de noeuds dans le graphe. Dans le pire des cas, l'algorithme doit visiter chaque nœud dans le graphe. Arbre Graphiques
Dans le contexte des graphes , un arbre est un graphe dans lequel chaque noeud à l'exception du nœud origine "root" a un nœud parent unique dont la lignée remonte au nœud racine. Le graphique forme une structure semblable à celle d'un arbre de Noël, et en élargissant progressivement l'ajout de nouveaux noeuds et les enfants à chaque niveau. Dans un arbre , le nombre d'enfants chaque noeud a est le « facteur de branchement . " De l'arbre , le nombre de générations dans l'arbre est l'arbre " de profondeur . "
Profondeur d'abord
profondeur d'abord est une méthode de recherche par le biais d'un arbre , dans lequel l'algorithme descend de l'arbre jusqu'à ce qu'il trouve le nœud cible . A partir du noeud racine , l'algorithme descend à l'enfant suivant , puis le petit-fils de cet enfant , répétant le processus jusqu'à ce qu'il trouve un noeud sans enfant "feuille " . Après elle constate que nœud, il marche arrière jusqu'à ce qu'il trouve un noeud non examinée . S'il n'y a pas ganglions examinés plus , il s'arrête.
Algorithme complexité en temps
Le temps de traverser un arbre via profondeur d'abord en fonction du nombre de sommets dans le graphe et les bords entre eux. Dans le pire des cas, l'algorithme doit voyager par tous les sommets et le long de chaque bord , donc le temps qu'il faudra est le nombre de sommets et le nombre d'arêtes , ou « V + E." Pour un arbre , le nombre de bords est égale aux nœuds moins un, de sorte que la durée totale est " 2V - 1. « Si chaque nœud dans le graphe a le même nombre d'enfants - un facteur de branchement constant - alors cette fois est égale à ce facteur . élevé à la puissance de la profondeur de l' arbre
Autres considérations
Lorsque la mise en œuvre n'importe quel algorithme , la vitesse de l'algorithme dépend de deux facteurs : le nombre de calculs, il faut faire et le temps requis pour accéder aux ressources dont il a besoin pour fonctionner - habituellement mémoire . La mémoire de plus d'un programme nécessite , plus il faut courir. Une profondeur d'abord ne doit pas oublier les nœuds précédents qu'elle a visités , de sorte que le montant de la pire de mémoire requise est égal au nombre de nœuds dans l'arbre.
|
