Parcours en largeur des graphes

L'autre façon de parcourir un graphe est en largeur (d'abord). Les sommets de la figure 2.10 ont été numérotés dans l'ordre du parcours en largeur. On ne peut pas programmer récursivement ce parcours de façon naturelle. Sa version itérative utilise la structure de file au lieu de celle de pile.

  public static void parcoursLargeur(Graphe g,
                                     Traitement v) {
    Iterator j = g.sommets();
    Set sommetsVisités = new HashSet();
    while (j.hasNext()) {
      Sommet s = (Sommet) j.next();
      if (!sommetsVisités.contains(s)) {
        parcoursLargeur(s, sommetsVisités, v);
      }
    }
  }

  static void parcoursLargeur(Sommet origine, 
                              Set sommetsVisités,
                              Traitement v) {
    File file = new FileParListe() ;
    file.enfiler(origine);
    sommetsVisités.add(origine);
    while (!file.estVide()) {
      Sommet s = (Sommet) file.défiler();
      v.traite(s);
      Iterator i = s.adjacents();
      while (i.hasNext()) { 
        Sommet suivant = (Sommet) i.next();
        if (!sommetsVisités.contains(suivant)) {
          file.enfiler(suivant);
          sommetsVisités.add(suivant);
        }
      }
    }
  }

Cette fonction a exactement la même forme que celle implémentant le parcours itératif en profondeur, les piles étant simplement remplacées par les files, avec leurs opérations : ceci est un indice du pouvoir structurant des structures de données.

Comme pour le parcours en profondeur, le parcours en largeur construit implicitement une arborescence couvrante (ou une forêt d'arborescences) ; il suffirait d'insérer l'affectation suivante après l'entrée dans la file du sommet suivant :

         suivant.chgParent(s);

En outre, le parcours en largeur permet d'énumérer les sommets par ordre de niveau d'accessibilité (c'est-à-dire de nombre d'arcs depuis l'origine) croissant, l'origine ayant le niveau 0. Il suffirait d'ajouter à l'interface Sommet une méthode qui incrémente le niveau d'un sommet, et d'insérer l'instruction suivante :

         suivant.incrémenteNiveau();