Degrés et sources — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 7)

Degrés et sources

Graphes sans circuit et ordonnancement de projets · niveau 2

Énoncé

Le degré sortant d'un sommet est le nombre d'arcs qui en partent, son degré entrant le nombre d'arcs qui y arrivent.

Écrire int[] degresSortants(Liste[] G) et int[] degresEntrants(Liste[] G) en $Θ (n + m)$ , sans construire le graphe symétrique.
En déduire une fonction Liste sources(Liste[] G) qui retourne la liste des sources du graphe, par numéros croissants.
Donner les deux tableaux de degrés pour le réseau de bus de l'exercice 7.2.

Corrigé

Un arc $i \to j$ se lit dans la liste $G [i]$ : il ajoute $1$ au degré sortant de $i$ et $1$ au degré entrant de $j$ .


static int[] degresSortants(Liste[] G) { int n = G.length;
    int[] DS = new int[n];
    for (int i = 0; i < n; i++)
        for (Liste l = G[i]; !vide(l); l = reste(l)) DS[i]++;
    return DS;
}
static int[] degresEntrants(Liste[] G) { int n = G.length;
    int[] DE = new int[n];
    for (int i = 0; i < n; i++)
        for (Liste l = G[i]; !vide(l); l = reste(l)) DE[premier(l)]++; // arc i --> premier(l)
    return DE;
}
static Liste sources(Liste[] G) {
    int[] DE = degresEntrants(G);
    Liste S = null;
    for (int i = G.length - 1; i >= 0; i--)      // i décroissants : liste croissante
        if (DE[i] == 0) S = new Liste(i, S);
    return S;
}

Les deux doubles boucles touchent chaque sommet et chaque arc une fois : $Θ (n + m)$ . Sur le réseau de bus :


DS = [3, 2, 2, 1, 0], DE = [0, 1, 1, 2, 4]

La seule source est la ville $0$ .