Parcours en profondeur des graphes

Comme pour les structures de données élémentaires (ensembles, listes, tables), un graphe peut être sujet à l'énumération de ses sommets ou de ses arcs ; un sommet peut aussi être sujet à l'énumération des sommets adjacents. Les interfaces des graphes et des sommets doivent comporter les itérateurs suivants, chacun devant implémenter les méthodes hasNext() et next() (le pattern d'itération est décrit au § 3.11) :

interface Graphe {
  // ...
  Iterator sommets();
  Iterator arcs();
}

interface Sommet {
  // ...
  Iterator adjacents();
}

L'implémentation de la méthode adjacents() dépend évidemment de la structure de données utilisée pour représenter un graphe : matrice d'adjacence ou ensemble d'adjacence.

Parcourir un graphe consiste à choisir un sommet et à énumérer à partir de celui-ci ses sommets en suivant ses arcs autant que possible ; chaque sommet énuméré peut donner lieu à un traitement (par exemple, imprimer une information associée au sommet). Il y deux parcours classiques. Si un parcours énumère un sommet u, puis un sommet adjacent v, un parcours en profondeur va énumérer les sommets adjacents à v avant d'énumérer les sommets adjacents à u autres que v, et un parcours en largeur adopte le choix inverse. Comme un sommet peut être adjacent à plusieurs sommets, il faut prendre garde à ne pas énumérer plusieurs fois le même sommet ; en outre, comme un graphe peut comporter des circuits, ceci risquerait de produire une énumération infinie. Il faut donc marquer les sommets déjà énumérés. Quand on réalise un parcours sur une feuille de papier, on colorie ces sommets au fur et à mesure du parcours ; dans un programme, on utilise une structure de données, par exemple un ensemble, pour stocker les sommets énumérés.

Nous allons rassembler les algorithmes sur les graphes dans une classe Algorithmes du package graphe. Le parcours en profondeur est très facile à programmer dans sa version récursive ; s'il s'agit simplement d'imprimer les valeurs des nuds, un par ligne, on écrira la fonction suivante :

package graphe;
import java.util.Set;

public class Algorithmes {

  static void parcoursProfondeur(Sommet origine, 
                                 Set sommetsVisités) {
    sommetsVisités.add(origine);
    System.out.println(origine.getIndice());
    Iterator i = origine.adjacents();
    while (i.hasNext()) { 
      Sommet suivant = (Sommet)i.next();
      if (!sommetsVisités.contains(suivant)) {
        parcoursProfondeur(suivant, sommetsVisités);
      }
    }
  }
}

Un parcours en profondeur construit implicitement une arborescence qui a la même structure que l'arbre d'invocation de la fonction récursive parcoursProfondeur(). Pour rendre cette arborescence explicite, il suffirait d'ajouter un champ parent aux sommets pour enregistrer le prédécesseur de chaque sommet énuméré, et d'insérer juste avant l'invocation récursive l'affectation (ceci suppose que l'interface Sommet soit enrichie d'une méthode chgParent()) :

  suivant.chgParent(origine);

Ce parcours en profondeur n'atteint que les sommets accessibles depuis l'origine. Pour parcourir l'ensemble des sommets d'un graphe g, il faut être capable d'énumérer tous les sommets (dans un ordre quelconque), et il faut relancer un parcours en profondeur à partir d'une origine qui n'a pas encore été énumérée, tant qu'il en existe :

package graphe;
import java.util.Set;
import java.util.HashSet;

public class Algorithmes {

  public static void parcoursProfondeur(Graphe g) {
    Iterator j = g.sommets();
    Set sommetsVisités = new HashSet();
    while (j.hasNext()) {
      Sommet s = (Sommet) j.next();
      if (!sommetsVisités.contains(s)) {
        parcoursProfondeur(s, sommetsVisités);
      }
    }
  }
  static void parcoursProfondeur(Sommet origine, 
                                 Set sommetsVisités) {
  // comme ci-dessus
  }
}

On invoquera Algorithmes.parcoursProfondeur(g), pour un graphe g.