Parcours d’arbres

Pour parcourir un graphe, nous construisons d’abord un arbre couvrant de ce dernier.

Parcours en largeur

Dans le parcours en largeur, on parcourt par profondeur croissante à la racine.

arbre5

ParcoursLargeur(Graphe G, Sommet s):
{
  f = CreerFile();
  f.enfiler(s);
  marquer(s);
  tant que non f.vide()
      s = f.defiler();
      afficher(s);
      pour tout voisin t de s dans G
           si t non marqué FAIRE
                f.enfiler(t);
                marquer(t);
           fin si
      fin pour
  fin tant que       
 }

Parcours en profondeur : préfixe

Les parcours en profondeur sont des parcours récursifs. Dans le parcours préfixe, nous parcourons toujours le sous-arbre gauche avant de traiter le sous-arbre droit.

arbre6

ParcoursPrefixe(Graphe G):
{
  si (G==NULL) return;
  afficher(racine);
  ParcoursPrefixe(a.gauche);
  ParcoursPrefixe(a.droite);      
 }

Parcours en profondeur : infixe

Le parcours en profondeur en infixe consiste à aller le plus à gauche possible, et d’afficher les branches de gauche à droite. Cela revient à afficher les diagonales / de bas en haut.

arbre7

 ParcoursInfixe(Graphe G):
{
  si (G==NULL) return;
  ParcoursPrefixe(a.gauche);
  afficher(racine);
  ParcoursPrefixe(a.droite);      
 }

Parcours en profondeur : postfixe

Il s’agit d’un parcours des diagonales \  de haut en bas.

arbre8

 ParcoursPostfixe(Graphe G):
{
  si (G==NULL) return;
  ParcoursPrefixe(a.gauche);
  ParcoursPrefixe(a.droite);
  afficher(racine);   
 }
Publicités