Parcours de graphe
Cette feuille en Postscript

1  Notre amie, la classe des listes

class List {
  int val ;  List next ;

  List (int val, List next) {
    this.val = val ; this.next = next ;
  }
}
  1. Comment représenter la liste vide ? Si p est de type List, peut on toujours faire p.val ?
  2. Comment définir et initialiser une variable p à la liste 1, 2, 3 ?
  3. Comment comprendre l'affectation this.next =next ? Proposer un codage qui évite this.
Solution.

2  Une structure de donnée très abstraite

interface Bag {
  boolean isEmpty () ;
  void add(int s) ; // Ajoute un élément au sac.
  int get() ;       // Renvoie (et enlève) un élement du sac.
}
  1. Comment comprendre cette construction bizarre de Java ? De quoi nos sacs sont-ils des sacs ? Les sacs sont-ils des ensembles ?
  2. À priori, que fait ce petit code :
    // b est un Bag
           for (int i = 0 ; i < 16 ; i++)
         b.add(i) ;
           while (!b.isEmpty())
         System.out.println(b.get()) ;
    Qu'obtient-on si le sac est une pile, une file ?
  3. Écrire une classe Lifo des piles implémentant l'interface Bag.
Solution.

3  Réalisation des graphes

class Graph { // Graphes non-orientés
  static List [] succ ;

  static void empty(int size) { succ  = new List[size] ;}

  static void add(int src, int dst) {
    succ[src] = new List (dst,succ[src]) ;
    succ[dst] = new List (src,succ[dst]) ;
  }
  1. Allocations : Que font succ[src] = new List (dst, succ[src]) et succ = new List [size] ?
  2. Où sont les sommets et les arcs dans cette représentation des graphes ?
  3. Justifier le commentaire. Comment faire une classe des graphes orientés ?
  4. Construire ce graphe :
  5. Une particularité de l'allocation des tableaux (d'objets) garantit la correction de notre représentation, laquelle ? Qu'en est-il des tableaux de scalaires ?
Solution.

4  Réalisation du parcours avec un sac

On choisit un parcours du graphe particulièrement abstrait :
  static void xfs(int s, Bag b) {
    boolean [] vu = new boolean[succ.length] ;

    b.add(s) ; vu[s] = true ;
    do  {
      int n = b.get() ;
      System.out.print(" " + n) ;
      for (List p = succ[n] ; p != null ; p = p.next)
        if (!vu[p.val]) {
          b.add(p.val) ; vu[p.val] = true ;
        }
    } while (!b.isEmpty()) ;
  }
  1. Peut-on se passer de la variable n ?
  2. Commençons par prouver la terminaison. On pourra chercher à partitioner l'ensemble des sommets en trois.
  3. Poursuivons par la correction ainsi exprimée : notre méthode affiche la composante connexe de s.
  4. Enfin terminons par le coût, montrer que le parcours est en O(V+E), où V est le nombre de sommets et E le nombre d'arcs (de la composante connexe de s).
  5. Comment procéder pour afficher toutes les composantes connexes du graphe ?
Solution.

5  Arbre de recouvrement

Voici une variation sur parcours avec un sac.
  static int [] findSpanningTree(int s, Bag b) {
    int [] pere = new int[succ.length] ;

    for (int i = pere.length-1 ; i >= 0 ; i--)
      pere[i] = -1 ;

    b.add(s) ; pere[s] = s ; // par convention
    do {
      int n = b.get() ;
      for (List p = succ[n] ; p != null ; p = p.next)
        if (pere[p.val] < 0) {
          b.add(p.val) ; pere[p.val] = n;
        }
    } while (!b.isEmpty()) ;
    return pere ;
  }
  1. Quelle est l'objet renvoyé ? Pourquoi le tableau pere est-il initialisé explicitement ?
  2. Je prétends que cette méthode renvoie un arbre. Comment est-il représenté ? Donner des arbres possibles dans le cas où le sac est une file, une pile (départ en zéro).
  3. Je prétend encore que cet arbre est un arbre de recouvrement de la composante connexe de s. Ai-je raison ?
  4. Notre programme peut-il produire n'importe quel arbre de recouvrement ?
  5. Comment faire pour, étant donnés deux sommets s et s', afficher un chemin de s à s' si il en existe ?
  6. Comment faire pour, étant donnés deux sommets s et s', afficher un plus court chemin de s à s' si il en existe ?
Solution.

6  Parcours en profondeur d'abord

Dans la question précédente, nous avons vu que le codage en pratique du parcours en largeur d'abord peut s'éloigner un peu de du codage avec un sac. Voici le parcours en profondeur programmé récursivement. (l'arbre de recouvrement est affiché à la volée).
  static private void doDfs (int s, int pere,boolean [] vu) {

    if (vu[s]) return ;
    vu[s] = true ;
    System.out.print (" " + s + "<" + pere + ">") ;
    for (List p = succ[s] ; p != null ; p = p.next) {
      doDfs(p.val, s, vu) ;
    }
  }

  static void dfs(int s) {
    boolean [] vu = new boolean [succ.length] ;

    doDfs(s,s,vu) ;
  }
  1. Modifier le programme pour qu'il numérote les sommets dans l'ordre du parcours (numérotation préfixe de l'arbre de recouvrement).
  2. Obtenir une numérotation suffixe de l'arbre de recouvrement.
  3. Programmer un véritable parcours en profondeur d'abord avec une pile explicite.
Solution.

Ce document a été traduit de LATEX par HEVEA et HACHA.