Parcours de Graphes

Pour chercher dans un graphe (parcours de Graphes), on construit d’abord un arbre couvrant le graphe.

Breadth-first search / Recherche en profondeur

BFS parcourt l’arbre en augmentant la profondeur jusqu’à la racine.

Breadth first search Parcours de Graphes
BFS(Graph G, Node s):
{
  f = CreateQueue();
  f.stack(s);
  mark(s);
  while non f.empty()
      s = f.pop();
      print(s);
      for each children t of s in G
           if t unmarked DO
                f.stack(t);
                mark(t);
           end if
      end for
  end while       
 }

In-depth search : pre-order

Les algorithmes en profondeur sont récursifs. Dans le chemin du préfixe, nous parcourons toujours le sous-arbre de gauche avant de traiter le sous-arbre de droite.

In-depth search : pre-order
  1. Vérifiez si le nœud actuel est vide ou nul.
  2. Affiche la partie données de la racine (ou du nœud actuel).
  3. Parcourez le sous-arbre de gauche en appelant de manière récursive la fonction de pré-ordre.
  4. Parcourez le sous-arbre de droite en appelant de manière récursive la fonction de pré-ordre.

In-depth search : in-order

Le LNR parcourt le plus à gauche possible, et affiche les branches de gauche à droite. Cet algorithme affiche les diagonales de bas en haut.

In-depth search : in-order
  1. Vérifiez si le nœud actuel est vide ou nul.
  2. Parcourez le sous-arbre de gauche en appelant de manière récursive la fonction in-order.
  3. Affiche la partie données de la racine (ou du nœud actuel).
  4. Parcourez le sous-arbre de droite en appelant de manière récursive la fonction in-order.

In-depth search : out-order

Il s’agit d’une navigation en diagonale de haut en bas.

In-depth search : out-order
  1. Vérifiez si le nœud actuel est vide ou nul.
  2. Parcourez le sous-arbre de gauche en appelant de manière récursive la fonction de post-ordre.
  3. Parcourez le sous-arbre de droite en appelant de manière récursive la fonction de post-ordre.
  4. Affiche la partie données de la racine (ou du nœud actuel).
Partager
fr_FRFR
%d blogueurs aiment cette page :