Graphes sans circuit et ordonnancement de projets

Jusqu'ici, nos sous-problèmes étaient rangés dans des tableaux : l'objet $k$ venait après l'objet $k-1$, la case $(l,c)$ après les cases $(l-1,\cdot )$. Dans ce chapitre, la structure des sous-problèmes est donnée par un graphe : la tâche $j$ d'un projet ne peut commencer qu'après certaines autres tâches, ses prédécesseurs. La programmation dynamique s'applique toujours, à condition de calculer les valeurs dans un ordre où les prédécesseurs passent avant leurs successeurs.

7.1 Listes d'entiers

La définition est récursive : la liste que nous écrivons $(0212)$ est, pour l'ordinateur, le couple $(0(2(1(2()))))$. En Java, la liste vide est représentée par null et un couple par un objet de la classe Liste :

static class Liste { int p; Liste r;    // premier et reste
    Liste(int p, Liste r) { this.p = p; this.r = r; }
}
static boolean vide(Liste l)  { return l == null; }
static int     premier(Liste l) { return l.p; }   // l non vide
static Liste   reste(Liste l)   { return l.r; }   // l non vide

La liste $(0212)$ se construit par new Liste(0, new Liste(2, new Liste(1, new Liste(2, null)))). Ajouter un élément $x$ en tête d'une liste $l$ est en temps constant : l = new Liste(x, l). Le parcours d'une liste s'écrit avec une boucle for :

for (Liste l = L; !vide(l); l = reste(l))
    System.out.print(premier(l) + " ");

Les fonctions sur les listes s'écrivent naturellement de façon récursive, en suivant la définition : un cas pour la liste vide (base), un cas pour la liste non vide (hérédité).

static int longueur(Liste l) {
    if (vide(l)) return 0;              // la liste vide a 0 élément
    return 1 + longueur(reste(l));      // le premier, plus ceux du reste
}

7.2 Graphes orientés

7.2.1 Représentation par un tableau de listes d'arcs

On représente un graphe à $n$ sommets par un tableau $G[0:n]$ de listes : $G[i]$ est la liste des successeurs de $i$, c'est-à-dire la liste des arcs qui sortent de $i$. L'ordre des éléments d'une liste est quelconque.

static Liste[] graphe() {   // G[i] = liste des successeurs de i
    Liste[] G = new Liste[8];
    G[0] = new Liste(1, new Liste(2, new Liste(3, null)));
    G[1] = new Liste(3, new Liste(5, null));
    G[2] = new Liste(4, new Liste(5, new Liste(6, new Liste(7, null))));
    G[3] = new Liste(7, null);
    G[4] = new Liste(6, new Liste(7, null));
    G[5] = new Liste(6, new Liste(7, null));
    G[6] = new Liste(7, null);
    G[7] = null;
    return G;
}
static void afficher(Liste[] G) {
    for (int i = 0; i < G.length; i++) {
        System.out.print(i + " :");
        for (Liste l = G[i]; !vide(l); l = reste(l))
            System.out.print(" " + premier(l));
        System.out.println();
    }
}

Cette représentation occupe une place proportionnelle à $n+m$ : une case de tableau par sommet, une cellule de liste par arc. Elle permet de parcourir les successeurs d'un sommet en un temps proportionnel à leur nombre.

7.2.2 Le graphe symétrique

Les récurrences de ce chapitre s'expriment avec les prédécesseurs d'un sommet, alors que $G[j]$ donne ses successeurs. On construit donc le graphe symétrique.

static Liste[] symetrique(Liste[] G) { int n = G.length;
    Liste[] Gp = new Liste[n];                  // n listes vides
    for (int i = 0; i < n; i++)
        for (Liste l = G[i]; !vide(l); l = reste(l)) { int j = premier(l);
            Gp[j] = new Liste(i, Gp[j]);            // arc j --> i ajouté à G'
        }
    return Gp;
}

Chaque sommet est touché une fois (boucle externe), chaque arc une fois (boucle interne), et le corps de boucle est en temps constant puisque l'ajout se fait en tête de liste. Le temps de calcul est de la forme $\alpha (n+m)+\beta$ : la complexité est $\Theta (n+m)$, linéaire en la taille du graphe. On ne peut pas faire mieux, puisqu'il faut au moins lire le graphe.

Graphe symétrique G' :
0 :
1 : 0
2 : 0
3 : 1 0
4 : 2
5 : 2 1
6 : 5 4 2
7 : 6 5 4 3 2

7.3 Numérotation isotone