Complexité du temps DFS

DFS signifie une recherche en profondeur d'abord. Il se réfère à la façon dont les nœuds d'un arbre sont visités jusqu'à ce que le nœud souhaité soit situé. Pour plus de simplicité, tous les nœuds de cet article seront visités. L'idée est de voir tous les nœuds, avec chaque nœud visité une fois. Un nœud est également appelé sommet. La recherche en profondeur d'abord peut être dans l'un des trois ordres: pré-commande, ordre ou post-ordre. La traversée de précommande est utilisée dans cet article. Cet article utilise l'arborescence suivante pour illustrer la précommande pour la recherche en profondeur d'abord:

Une branche dans l'arbre est appelée un bord. Cet article vise à illustrer ce que l'on appelle la complexité temporelle pour la recherche en profondeur d'abord. DFS est d'abord expliqué brièvement. C ++ est utilisé pour l'illustration de code.

Traversion de précommande pour la recherche en profondeur d'abord

L'algorithme est le suivant:

1) Visitez le sommet actuel.
2) Traverser le sous-arbre gauche du sommet actuel de manière récursive.
3) Traverser le sous-arbre droit du sommet actuel de manière récursive.

Pour l'arbre précédent, le premier sommet à visiter est un. C'est le sommet actuel. Traverser récursivement le sous-arbre gauche, puis le sous-arbre droit signifie visiter b tandis que la visite de C est enregistrée dans la mémoire à visiter plus tard.

À B, B est le sommet actuel. Traverser récursivement le sous-arbre gauche, puis le sous-arbre droit signifie visiter E pendant que la visite de F est enregistrée dans la mémoire à visiter plus tard.

À e, e est le sommet actuel. E n'a pas de sous-arbre gauche ou droit (pas de bords). Le dernier enregistrement en mémoire pour la visite était le bon sous-arbre (bord) pour b. Le sous-arbre droit pour B se compose de F précédé par son bord. À ce stade, F est visité.

L'enregistrement précédent en mémoire pour visiter maintenant est le bon sous-arbre (bord) pour un. Le sous-arbre droit pour un enregistré se compose de C suivi par ses bords et ses enfants. À ce stade, C est visité. C a trois bords. Selon l'algorithme, le bord gauche est accessible en premier.

Lorsque le bord gauche est accessible, G est visité. Il n'y a pas d'enfant pour g. Par l'algorithme, H partage le même parent avec G, et comme c'est à droite de G, il est visité ensuite.

«Je» se trouve être à droite de H et partage le même parent avec H. Par l'algorithme, tout nœud à droite d'un autre nœud doit être visité après la visite du nœud. Peu importe si le nœud qui vient d'être visité est à droite d'un autre nœud. Alors «je» est visité ensuite.

Il n'y a pas de nœud à droite de «I». C et tous ses descendants ont été visités. Cependant, notez qu'il y a un nœud à droite de C. Ce nœud est D. Par l'algorithme, tout nœud à droite d'un autre nœud doit être visité après le nœud (visité). Peu importe si le nœud visité était à droite d'un autre nœud. Donc D est visité ensuite.

D a deux enfants, J et K. J est à gauche de K. J est visité avant K.

L'algorithme de recherche en profondeur d'abord peut être résumé comme suit: Après avoir visité la racine, visitez le sommet gauche tout en descendant récursivement à gauche. Du sommet le plus à gauche, visitez les frères et sœurs droits de ce sommet, puis montez récursivement l'arbre, vers la droite et descendez de temps en temps.

Avec cela, la séquence DFS de l'arbre précédent est: a, b, e, f, c, g, h, i, d, j, k.

Complexité temporelle

L'arbre précédent a 11 sommets et 10 bords. Si l'arbre est bien stocké, le balayage de l'arbre entier impliquera 11 sommets et 10 bords. Ceci est une appréciation de la vitesse de fonctionnement de la recherche en profondeur d'abord. C'est la complexité du temps. Il est écrit comme:

O (| v | + | e |)

Où | V | est le nombre de sommets (nœuds) et | e | est le nombre d'arêtes. Pour cet arbre, le total est de 21 = 11 + 10. Le «O» doit être là.

Structure de l'arbre

L'organisation des arbres peut être décrite comme suit:

Vertex A: Enfants: B, C, D
Vertex B: Enfants: E, F
Vertex C: Enfants: G, H, I
Vertex D: Enfants: J, K
Sommet e
Vertex F
Vertex g
Sommet h
Vertex I
Vertex J
Vertex k

L'arbre précédent sera stocké dans un non ordonné de vecteurs. Un sommet est une clé, et les enfants sont les valeurs du vecteur de la clé. Les sommets de E à K n'ont pas d'enfants.

Codage C ++

Le programme peut commencer par le titre suivant:

#inclure
#inclure
#inclure
Utilisation de Namespace Std;

C ++ codage pour les vecteurs non ordonnés

Le vecteurs non ordonnés_map-de-trait est créé avec le code suivant:

non ordonné_map > umv = 'a', 'b', 'c', 'd',
'B', 'e', 'f',
'C', 'g', 'h', 'i',
'D', 'j', 'k',
'E', ,
'F', ,
'G', ,
'H', ,
'JE', ,
'J', ,
'K', ;

Cela peut être placé juste en dessous de la rubrique précédente.

La fonction de profondeur d'abord

Il s'agit d'une fonction récursive qui imprime chaque sommet (nœud) visité. C'est:

void DepthFirstSearch (Char Parent)
couter << parent << "; //print vertex
pour (int i = 0; iDepthFirstSearch (UMV [parent] [i]);

Après avoir imprimé le sommet gauche, la boucle pour imprimerait les sommets droits. La boucle forte a le rappel.

C ++ Fonction principale

Une fonction principale appropriée pour le programme est:

int main (int argc, char ** argv)

DepthFirstSearch («a»);
couter << endl;
retour 0;

L'algorithme pour la recherche en profondeur d'abord est le suivant:

1) Visitez le sommet actuel.
2) Traverser le sous-arbre gauche du sommet actuel de manière récursive.
3) Traverser le sous-arbre droit du sommet actuel de manière récursive.

Cela peut être interprété comme suit: Après avoir visité la racine, visitez le sommet gauche, en descendant récursivement à gauche. Du sommet le plus à gauche, visitez les frères et sœurs droits de ce sommet et montez récursivement l'arbre, vers la droite, descendant de temps en temps, de manière appropriée.

La complexité temporelle de l'algorithme de recherche en profondeur d'abord est:

O (| v | + | e |)

Conclusion

DFS signifie une recherche en profondeur d'abord. Il se réfère à la façon dont les nœuds d'un arbre sont visités jusqu'à ce que le nœud souhaité soit situé. Pour plus de simplicité, tous les nœuds de l'arbre de cet article ont été visités. L'idée est de visiter tous les nœuds, avec chaque nœud visité une fois. Un nœud est également appelé sommet. La recherche en profondeur d'abord peut être dans l'un des trois ordres: pré-commande, ordre ou post-ordre. Dans cet article, la traversée de précommande a été utilisée.