Itération préfixe d'un graphe

La structure de pile permet de définir un itérateur préfixe sur les graphes, qui réalise un parcours en profondeur du graphe avec une énumération préfixe des sommets. La définition de cet itérateur utilise deux autres itérateurs, l'un, j, pour énumérer tous les sommets (ce qui est nécessaire si tous les sommets ne sont pas accessibles), l'autre, i, pour énumérer les sommets adjacents à un sommet :

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

public class Prefixe implements Iterator {
  Set sommetsVisités;
  Pile pile;
  Iterator j;
  public Prefixe(Graphe g) {
    sommetsVisités = new HashSet();
    pile = new PileParListe();
    j = g.sommets();  
    if (j.hasNext()) pile.empiler(j.next());
  }

  public boolean hasNext() {
    if (pile.estVide()) {
      while (j.hasNext()) {
        Sommet s = (Sommet) j.next();
        if (!sommetsVisités.contains(s)) {
          pile.empiler(s);
          return true;
        }
      }
      return false;
    } else {
      return true;
    }
  }

  public Object next() {
    if (pile.estVide()) {
      while (j.hasNext()) {
        Sommet s = (Sommet) j.next();
        if (!sommetsVisités.contains(s)) {
          sommetsVisités.add(s);
          Iterator i = s.adjacents();
          while (i.hasNext()) { 
            Sommet suivant = (Sommet) i.next();
            if (!sommetsVisités.contains(suivant)) {
              pile.empiler(suivant);
            }
          }
          return s;
        }
      }
      throw new NoSuchElementException();
    } else {
      Sommet s = (Sommet) pile.dépiler();
      sommetsVisités.add(s);
      Iterator i = s.adjacents();
      while (i.hasNext()) { 
        Sommet suivant = (Sommet) i.next();
        if (!sommetsVisités.contains(suivant)) {
          pile.empiler(suivant);
        }
      }
      return s;
    }
  } 

  public void remove() {
    throw new UnsupportedOperationException();
  } 
}

On l'utilisera de la façon suivante :

    Iterator i = new Prefixe(g); 
    while (i.hasNext())  
      System.out.println((Sommet) i.next());

De façon analogue, la structure de file permet de définir un itérateur en largeur sur les graphes :

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

public class EnLargeur implements Iterator {
  Set sommetsVisités;
  File file;
  Iterator j;
  public EnLargeur(Graphe g) {
    sommetsVisités = new HashSet();
    file = new FileParListe();
    j = g.sommets();  
    if (j.hasNext()) {
      Sommet s = (Sommet) j.next();
      file.enfiler(s);
      sommetsVisités.add(s);
    }
  }

  public boolean hasNext() {
    if (file.estVide()) {
      while (j.hasNext()) {
        Sommet s = (Sommet) j.next();
        if (!sommetsVisités.contains(s)) {
          file.enfiler(s);
          sommetsVisités.add(s);
          return true;
        }
      }
      return false;
    } else {
      return true;
    }
  }

  public Object next() {
    if (file.estVide()) {
      while (j.hasNext()) {
        Sommet s = (Sommet) j.next();
        if (!sommetsVisités.contains(s)) {
          Iterator i = s.adjacents();
          while (i.hasNext()) { 
            Sommet suivant = (Sommet) i.next();
            if (!sommetsVisités.contains(suivant)) {
              file.enfiler(suivant);
              sommetsVisités.add(s);
            }
          }
          sommetsVisités.add(s);
          return s;
        }
      }
      throw new NoSuchElementException();
    } else {
      Sommet s = (Sommet) file.défiler();
      Iterator i = s.adjacents();
      while (i.hasNext()) { 
        Sommet suivant = (Sommet) i.next();
        if (!sommetsVisités.contains(suivant)) {
          file.enfiler(suivant);
          sommetsVisités.add(suivant);
        }
      }
      return s;
    }
  } 

  public void remove() {
    throw new UnsupportedOperationException();
  } 
}