Détecter un circuit — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Détecter un circuit

Graphes sans circuit et ordonnancement de projets · niveau 3 (difficile)

Énoncé

La fonction numerotationIsotone du cours suppose le graphe sans circuit et de source unique.

Que se passe-t-il, dans la version du cours, si le graphe a un circuit ?
La modifier pour qu'elle accepte plusieurs sources et qu'elle retourne null si le graphe a un circuit. Indication : que se passe-t-il quand la file des sources devient vide avant que tous les sommets soient numérotés ?
Tester sur $C [0] = (1)$ , $C [1] = (2)$ , $C [2] = (31)$ , $C [3] = ()$ et sur un graphe à deux sources.

Corrigé

Les sommets d'un circuit ne deviennent jamais des sources : leur degré entrant ne tombe jamais à zéro. Dans la version du cours, la liste $L$ se vide alors que dnia < n - 1 : l'appel premier(L) sur une liste vide lève une NullPointerException.
On met toutes les sources initiales dans la file, et l'on s'arrête quand la file est vide ; il y a un circuit si et seulement si tous les sommets n'ont pas été numérotés.


static int[] numerotationIsotone(Liste[] G) { int n = G.length;
    int[] DE = degresEntrants(G), NI = new int[n];
    int[] file = new int[n]; int deb = 0, fin = 0;   // file[deb:fin] : sources à supprimer
    for (int i = 0; i < n; i++) if (DE[i] == 0) file[fin++] = i;
    int dnia = -1;                                   // dernier numéro attribué
    while (deb < fin) {
        int i = file[deb++];
        NI[i] = ++dnia;                              // i : source du graphe réduit
        for (Liste l = G[i]; !vide(l); l = reste(l)) { int j = premier(l);
            DE[j]--;                                 // arc i --> j supprimé
            if (DE[j] == 0) file[fin++] = j;         // j devient une source
        }
    }
    return (dnia == n - 1) ? NI : null;              // file vide trop tôt : circuit
}

Chaque sommet entre au plus une fois dans la file : $Θ (n + m)$ .

Exécution :


NI(C) = null
NI(deux sources) = [0, 1, 2, 3]

Dans $C$ , le circuit $1 \to 2 \to 1$ bloque tout après la source $0$ .