Séance 5 — Graphes

Parcourir, ordonner, trouver le plus court chemin et l’arbre couvrant minimal

Séance 5 de Structures de données et algorithmes avancés : parcourir, ordonner, trouver le plus court chemin et l’arbre couvrant minimal.

Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

Navigation conceptuelle

Amont. Les files et les piles (Séance 1) ; l’analyse du coût d’un algorithme (Séance 2) ; les listes chaînées des cases d’une table de hachage (Séance 3) ; les parcours préfixe et postfixe des arbres, et le tas binaire, qui réalise une file de priorité (Séance 4).

Aval. La Séance 6 traite les ensembles disjoints (Union-Find), qui remplacent le test de cycle de l’algorithme de Kruskal par une opération presque constante, puis les algorithmes de tri.

Objectifs

Modéliser un problème par un graphe (orienté ou non, pondéré ou non) et en lire le vocabulaire : degré, chemin, cycle, connexité.
Construire la matrice et les listes d’adjacence d’un graphe, et comparer leurs coûts en mémoire et en temps.
Dérouler un parcours en largeur (file, distances en nombre d’arêtes, arbre de parcours) et un parcours en profondeur (pile d’appels, ordres préfixe et postfixe).
Détecter un cycle dans un graphe orienté et produire un tri topologique par l’ordre postfixe inversé.
Dérouler l’algorithme de Dijkstra avec le tas de la Séance 4, et expliquer pourquoi un poids négatif le met en défaut.
Construire un arbre couvrant minimal par l’algorithme de Kruskal et mesurer le coût de son test de cycle.

Tous les programmes de ce document sont en Java ; ils ont été compilés par javac -Xlint:all et exécutés avec OpenJDK 21 sur Linux x86_64, et chaque sortie reproduite est celle de cette exécution. Les classes du cours sont Graphe (graphe orienté ou non, par listes d’adjacence), GraphePondere et Arete (graphes pondérés), ParcoursLargeur, ParcoursProfondeur, OrdreTopologique, CycleOriente, Dijkstra et Kruskal ; leurs compteurs publics (examines, extractions, perimees, visites) servent à observer le coût des algorithmes. Le tas est la classe BinaryMinHeap de la Séance 4.

Modéliser des relations

Les structures des séances précédentes rangent des données isolées : un numéro de téléphone, un matricule, une clé dans un arbre. Beaucoup de problèmes portent au contraire sur des relations entre données : deux villes reliées par une route, un cours qui en exige un autre, deux personnes qui se connaissent. Le graphe est la structure de ces relations. Le réseau suivant, qui sert de fil rouge, relie huit villes du centre et du sud du Sénégal par dix tronçons de route ; le nombre porté par chaque tronçon est sa longueur en kilomètres.

Graphe

Un graphe \(G=(V,E)\) est formé d’un ensemble \(V\) de sommets et d’un ensemble \(E\) d’arêtes ; chaque arête relie deux sommets, ses extrémités. Deux sommets reliés par une arête sont adjacents (ou voisins). Dans un graphe non orienté, l’arête \(v\)–\(w\) se parcourt dans les deux sens ; dans un graphe orienté, un arc \(v\to w\) ne se parcourt que de \(v\) vers \(w\). Un graphe est pondéré quand chaque arête porte un nombre, son poids.

Le réseau routier est un graphe non orienté et pondéré : \(|V|=8\), \(|E|=10\), et les dix poids totalisent \(1\,691\) km. Dans le code Java, les sommets sont les entiers \(0\) à \(V-1\) (les numéros gris de la figure), comme chez Sedgewick et Wayne ; un tableau de noms ne sert qu’à l’affichage. Les données du cours sont rangées dans la classe Reseau :

public static final String[] VILLES = {"Kaolack", "Kaffrine", "Tambacounda",
    "Kedougou", "Velingara", "Kolda", "Sedhiou", "Ziguinchor"};
public static final int[][] ROUTES = {  // {v, w, km}
    {0, 1, 63}, {0, 7, 251}, {0, 5, 272}, {1, 2, 210}, {2, 3, 233},
    {2, 4, 103}, {4, 5, 123}, {5, 6, 85}, {5, 7, 188}, {6, 7, 163}};

Le degré \(\deg(v)\) d’un sommet est le nombre d’arêtes dont il est une extrémité (dans un graphe orienté, on distingue le degré sortant et le degré entrant). Chaque arête a deux extrémités ; en additionnant les degrés de tous les sommets, chaque arête est donc comptée deux fois : \[\sum_{v\in V}\deg(v)=2\,|E|.\] Sur le réseau, les degrés de Kaolack à Ziguinchor valent \(3, 2, 3, 1, 2, 4, 2, 3\) : leur somme est \(20=2\times10\). Kolda, de degré 4, est le carrefour du réseau ; Kédougou, de degré 1, n’est relié qu’à Tambacounda.

Chemins, cycles, connexité

Un chemin est une suite de sommets \(v_0, v_1, \dots, v_k\) où chaque \(v_{i-1}\) est relié à \(v_i\) ; sa longueur est son nombre d’arêtes \(k\), ou, dans un graphe pondéré, la somme de leurs poids. Un cycle est un chemin d’au moins une arête qui revient à son départ sans repasser par une même arête. Un graphe non orienté est connexe si un chemin relie deux sommets quelconques ; sinon, il se découpe en composantes connexes. Un arbre est un graphe connexe sans cycle ; il a exactement \(V-1\) arêtes. Un graphe orienté sans cycle est un DAG (directed acyclic graph).

Le réseau est connexe et contient plusieurs cycles, par exemple Kolda–Sédhiou–Ziguinchor–Kolda ou Kaolack–Kolda–Ziguinchor–Kaolack. Les arbres de la Séance 4 sont des graphes particuliers : connexes, sans cycle, avec une racine.

Représenter un graphe

Un programme doit pouvoir répondre vite à deux questions : les sommets \(v\) et \(w\) sont-ils reliés ? Quels sont les voisins de \(v\) ? Deux représentations sont en usage.

Matrice d’adjacence, listes d’adjacence

La matrice d’adjacence est un tableau \(V\times V\) de booléens : a[v][w] est vrai si l’arête \(v\)–\(w\) existe ; elle est symétrique pour un graphe non orienté. Les listes d’adjacence associent à chaque sommet \(v\) la liste adj[v] de ses voisins.

La ligne 5 de la matrice (Kolda) contient quatre 1, autant que la liste 5 a d’éléments : c’est le degré de Kolda. La matrice range aussi les \(64-20=44\) zéros, alors que les listes ne contiennent que les \(2E=20\) entrées utiles. La classe Graphe du cours utilise les listes ; un booléen oriente décide si addEdge(v, w) range l’arête dans une seule liste (un arc) ou dans les deux. Le constructeur crée \(V\) listes vides ; l’annotation @SuppressWarnings évite l’avertissement de javac -Xlint:all sur la création d’un tableau de listes génériques, comme pour le tas de la Séance 4.

@SuppressWarnings({"unchecked", "rawtypes"})
public Graphe(int V, boolean oriente) {
    this.V = V;
    this.oriente = oriente;
    adj = (List<Integer>[]) new List[V];
    for (int v = 0; v < V; v++) adj[v] = new ArrayList<>();
}

private final int V;                // sommets 0..V-1
private final boolean oriente;
private int E;                      // aretes (ou arcs)
private final List<Integer>[] adj;  // adj[v] : voisins de v

public void addEdge(int v, int w) {
    adj[v].add(w);                // ajout en queue
    if (!oriente) adj[w].add(v);  // non oriente : aussi dans adj[w]
    E++;
}

public List<Integer> adj(int v) {
    return adj[v];
}

Exemple pas à pas : la construction des listes

Le programme suivant construit le réseau du cours à partir du tableau ROUTES de la classe Reseau, puis écrit le nombre de sommets et d’arêtes et la liste de Kolda.

Graphe g = new Graphe(8, false);
for (int[] r : ROUTES) g.addEdge(r[0], r[1]);
System.out.println(g.V() + " " + g.E());
System.out.println(g.adj(5));

Étape	Lignes	Instruction	Effet	Écrit
1	1	`Graphe g = new Graphe(8, false);`	8 listes vides, une par sommet (les villes sont numérotées de 0 à 7).
2	2	`g.addEdge(r[0], r[1]);`	`addEdge(0, 1)`, Kaolack–Kaffrine : 1 en queue de la liste 0, 0 en queue de la liste 1.
3	2	`g.addEdge(r[0], r[1]);`	`addEdge(0, 7)`, Kaolack–Ziguinchor : 7 en queue de la liste 0, 0 en queue de la liste 7.
4	2	`g.addEdge(r[0], r[1]);`	`addEdge(0, 5)`, Kaolack–Kolda : 5 en queue de la liste 0, 0 en queue de la liste 5.
5	2	`g.addEdge(r[0], r[1]);`	(suite) `addEdge(1, 2)`, Kaffrine–Tambacounda : une entrée dans chacune des deux listes.
6	2	`g.addEdge(r[0], r[1]);`	(suite) `addEdge(2, 3)`, Tambacounda–Kédougou : une entrée dans chacune des deux listes.
7	2	`g.addEdge(r[0], r[1]);`	(suite) `addEdge(2, 4)`, Tambacounda–Vélingara : une entrée dans chacune des deux listes.
8	2	`g.addEdge(r[0], r[1]);`	(suite) `addEdge(4, 5)`, Vélingara–Kolda : une entrée dans chacune des deux listes.
9	2	`g.addEdge(r[0], r[1]);`	(suite) `addEdge(5, 6)`, Kolda–Sédhiou : une entrée dans chacune des deux listes.
10	2	`g.addEdge(r[0], r[1]);`	(suite) `addEdge(5, 7)`, Kolda–Ziguinchor : une entrée dans chacune des deux listes.
11	2	`g.addEdge(r[0], r[1]);`	(suite) Dixième arête, Sédhiou–Ziguinchor : 10 arêtes, 20 entrées.
12	3	`System.out.println(g.V() + " " + g.E());`	8 sommets, 10 arêtes ; non orienté, chaque arête figure dans deux listes.	`8 10`
13	4	`System.out.println(g.adj(5));`	Les voisins de Kolda, dans l’ordre des ajouts : Kaolack, Vélingara, Sédhiou, Ziguinchor. Son degré est 4.	`[0, 4, 6, 7]`

Chaque appel de addEdge ajoute une entrée en queue de deux listes, comme l’ajout en queue du chaînage de la Séance 3 : l’ordre des voisins dans une liste est l’ordre des appels. Kaolack reçoit ainsi 1, puis 7, puis 5 ; Kolda reçoit 0 (l’arête Kaolack–Kolda, troisième du tableau), puis 4, 6 et 7. Cet ordre n’a pas d’importance pour le graphe lui-même, mais il décide de l’ordre dans lequel les parcours des sections suivantes examinent les voisins. Les états ci-dessous sont ceux des étapes 4 et 11 ; les entrées ajoutées à l’étape sont encadrées en rouge.

Étape 4 : addEdge(0, 5)

Étape 11 : addEdge(6, 7)

Sortie \(\rightarrow\)

8 10
[0, 4, 6, 7]

Les coûts des deux représentations

opération	matrice	listes
mémoire	\(\Theta(V^2)\)	\(\Theta(V+E)\)
l’arête \(v\)–\(w\) existe-t-elle ?	\(\Theta(1)\)	\(\mathcal{O}(\deg v)\)
parcourir les voisins de \(v\)	\(\Theta(V)\)	\(\Theta(\deg v)\)
parcourir tout le graphe	\(\Theta(V^2)\)	\(\Theta(V+E)\)

La matrice répond en temps constant à la question « \(v\) et \(w\) sont-ils reliés ? », mais elle coûte \(V^2\) cases quel que soit le nombre d’arêtes, et parcourir les voisins de \(v\) demande de lire toute la ligne \(v\). Les listes ne coûtent que ce que le graphe contient. Le choix dépend de la densité : un graphe est dense quand \(E\) est de l’ordre de \(V^2\), creux quand \(E\) est de l’ordre de \(V\). Un réseau routier est creux : une ville a quelques routes, pas des milliers. Pour \(V=10\,000\) villes et \(E=30\,000\) routes, la matrice compte \(10^8\) cases, et les listes \(2E=60\,000\) entrées. Le programme suivant mesure le travail d’un même parcours en largeur (section 3) sur les deux représentations de graphes au hasard : un anneau qui relie tous les sommets, complété par des cordes distinctes jusqu’à \(E=4V\) arêtes.

Random r = new Random(221);
for (int V : new int[] {1000, 2000, 4000}) {
    Graphe g = new Graphe(V, false);
    GrapheMatrice m = new GrapheMatrice(V);
    for (int[] a : Generateur.aretes(V, 4 * V, r)) {  // E = 4V
        g.addEdge(a[0], a[1]);
        m.addEdge(a[0], a[1]);
    }
    ParcoursLargeur p = new ParcoursLargeur(g, 0);
    long cases = m.parcoursLargeur(0);
    System.out.printf("V = %d, E = %d : listes %d lues, matrice %d lues%n",
        V, g.E(), p.examines, cases);
}

Sortie \(\rightarrow\)

V = 1000, E = 4000 : listes 8000 lues, matrice 1000000 lues
V = 2000, E = 8000 : listes 16000 lues, matrice 4000000 lues
V = 4000, E = 16000 : listes 32000 lues, matrice 16000000 lues

Les listes lisent exactement \(2E=8V\) entrées : chaque liste une fois. La matrice lit \(V^2\) cases : 125 fois plus pour \(V=1\,000\), 500 fois plus pour \(V=4\,000\). Quand \(V\) double, le travail des listes double et celui de la matrice quadruple. Le cours utilise donc les listes, comme Sedgewick et Wayne (§ 4.1).

Le parcours en largeur

Parcourir un graphe, c’est visiter tous les sommets que l’on peut atteindre depuis une source \(s\). Le problème est de ne jamais visiter deux fois le même sommet, alors que les cycles ramènent sans cesse vers des sommets déjà vus : chaque sommet porte une marque, posée à sa découverte. Le parcours en largeur explore le graphe par cercles concentriques : d’abord les voisins de \(s\), puis les voisins de ses voisins, et ainsi de suite.

Parcours en largeur (breadth-first search)

Marquer \(s\) et le mettre dans une file. Tant que la file n’est pas vide : retirer le sommet \(v\) de tête ; pour chaque voisin \(w\) de \(v\) non marqué, marquer \(w\), poser \(\texttt{edgeTo[w]}=v\) et \(\texttt{distTo[w]}=\texttt{distTo[v]}+1\), et mettre \(w\) en queue de la file.

La file est l’ArrayDeque du JDK (Séance 1, § 6.2) : add en queue, remove en tête. Un sommet est marqué au moment où il entre dans la file, pas au moment où il en sort : un sommet ne peut donc y entrer qu’une fois.

Exemple pas à pas : le réseau depuis Kaolack

Le programme suivant parcourt le réseau depuis Kaolack (sommet 0) ; marque, edgeTo et distTo sont des tableaux de 8 cases, nom le tableau des noms. Il écrit chaque ville au moment où elle sort de la file.

Queue<Integer> file = new ArrayDeque<>();
marque[0] = true;
file.add(0);
while (!file.isEmpty()) {
    int v = file.remove();
    System.out.print(nom[v] + " ");
    for (int w : g.adj(v)) {
        if (!marque[w]) {
            marque[w] = true;
            edgeTo[w] = v;
            distTo[w] = distTo[v] + 1;
            file.add(w);
        }
    }
}

Étape	Lignes	Instruction	Effet	Écrit
1	1–3	`file.add(0);`	Kaolack (0) est marqué et entre dans la file ; en gras, `distTo` : `distTo[0]` vaut 0.
2	5–12	`int v = file.remove();`	Kaolack sort ; ses voisins 1, 7, 5 sont marqués à distance 1 et entrent en file.	`Kaolack`
3	5–12	`int v = file.remove();`	Kaffrine sort ; Tambacounda est marqué à distance 2 et entre en file.	`Kaffrine`
4	5–12	`int v = file.remove();`	Ziguinchor sort ; Sédhiou est marqué à distance 2 et entre en file.	`Ziguinchor`
5	5–12	`int v = file.remove();`	Kolda sort ; Vélingara est marqué à distance 2 et entre en file.	`Kolda`
6	5–12	`int v = file.remove();`	Tambacounda sort ; Kédougou est marqué à distance 3 et entre en file.	`Tambacounda`
7	5–8	`int v = file.remove();`	Sédhiou sort ; tous ses voisins sont déjà marqués : la file ne reçoit rien.	`Sedhiou`
8	5–8	`int v = file.remove();`	Vélingara sort ; tous ses voisins sont déjà marqués : la file ne reçoit rien.	`Velingara`
9	5–8	`int v = file.remove();`	Kédougou (distance 3) sort, la file est vide ; en foncé, l’arbre de parcours.	`Kedougou`

Kaolack sort la première et découvre ses trois voisins, dans l’ordre de sa liste : Kaffrine, Ziguinchor et Kolda, à distance 1. Kaffrine sort ensuite et découvre Tambacounda ; Ziguinchor découvre Sédhiou ; Kolda découvre Vélingara, tous trois à distance 2. Quand Tambacounda sort, elle découvre Kédougou, à distance 3. Les trois derniers sommets ne découvrent plus rien : tous leurs voisins sont marqués. Les arêtes \(\texttt{edgeTo[w]}\)–\(w\) (en foncé) forment un arbre qui relie Kaolack aux sept autres villes : l’arbre de parcours.

Étape 4 : Ziguinchor sort

Étape 6 : Tambacounda sort

Sortie \(\rightarrow\)

Kaolack Kaffrine Ziguinchor Kolda Tambacounda Sedhiou Velingara Kedougou

Invariant de distTo

À tout instant, la file contient des sommets à distance \(d\) de \(s\), suivis de sommets à distance \(d+1\) : c’est vrai au départ (\(s\) seul, à distance 0), et retirer un sommet à distance \(d\) n’ajoute en queue que des sommets à distance \(d+1\). Les sommets sortent donc par distance croissante. Si un sommet \(w\) avait un chemin de \(k\) arêtes depuis \(s\) et recevait \(\texttt{distTo[w]}>k\), son prédécesseur \(u\) sur ce chemin, à distance au plus \(k-1\), serait sorti avant le sommet qui a découvert \(w\), et l’aurait découvert lui-même à distance au plus \(k\) : contradiction. distTo[w] est donc le plus petit nombre d’arêtes d’un chemin de \(s\) à \(w\).

Chaque sommet atteint entre une fois dans la file et en sort une fois, et sa liste est lue une fois : le parcours coûte \(\Theta(V+E)\) avec des listes. La mesure de la section 2 le confirme : exactement \(2E\) entrées lues.

Le chemin le plus court en tronçons

La classe ParcoursLargeur réalise ce parcours dans son constructeur (champs marque, edgeTo, distTo et la source s). Pour retrouver un chemin de \(s\) à \(v\), on remonte l’arbre de parcours depuis \(v\) par edgeTo, en ajoutant chaque sommet en tête d’une liste.

public List<Integer> chemin(int v) {
    if (!marque[v]) return null;
    LinkedList<Integer> c = new LinkedList<>();
    for (int x = v; x != s; x = edgeTo[x]) c.addFirst(x);
    c.addFirst(s);  // puis la source, en tete
    return c;
}
// dans main :
String[] nom = Reseau.VILLES;
ParcoursLargeur p = new ParcoursLargeur(Reseau.routes(), 0);
for (int v : new int[] {3, 4}) {
    System.out.println(nom[v] + " : " + p.distance(v) + " troncons, "
        + Reseau.noms(p.chemin(v), nom));
}

Sortie \(\rightarrow\)

Kedougou : 3 troncons, Kaolack Kaffrine Tambacounda Kedougou
Velingara : 2 troncons, Kaolack Kolda Velingara

Kédougou est à 3 tronçons de Kaolack, par Kaffrine et Tambacounda ; Vélingara à 2, par Kolda. Le parcours en largeur compte des tronçons, pas des kilomètres : Kaolack–Kolda–Vélingara mesure \(272+123=395\) km, alors que Kaolack–Kaffrine–Tambacounda–Vélingara, avec un tronçon de plus, ne mesure que \(63+210+103=376\) km. La section 6 traite ce problème.

Le parcours en profondeur

Le parcours en profondeur suit une autre stratégie : s’enfoncer aussi loin que possible le long d’un chemin, puis revenir en arrière dès qu’il n’y a plus de voisin nouveau. Il s’écrit naturellement par récursion ; la pile est alors celle des appels de méthode.

Parcours en profondeur (depth-first search)

dfs(v) : marquer \(v\), puis, pour chaque voisin \(w\) de \(v\) non marqué, appeler dfs(w), avant de passer au voisin suivant. L’ordre préfixe range \(v\) à l’entrée de dfs(v) ; l’ordre postfixe range \(v\) à la sortie de dfs(v), après tous les sommets atteints depuis \(v\).

Les deux ordres sont ceux des parcours d’arbres de la Séance 4 : préfixe, le nœud avant ses descendants ; postfixe, le nœud après eux. Chaque sommet est marqué une fois et chaque liste lue une fois : \(\Theta(V+E)\), comme la largeur.

Exemple pas à pas : le réseau depuis Kaolack

static void dfs(int v) {
    marque[v] = true;
    prefixe.add(v);
    for (int w : g.adj(v)) {
        if (!marque[w]) dfs(w);
    }
    postfixe.add(v);
}
// dans main :
dfs(0);
System.out.println(noms(prefixe));
System.out.println(noms(postfixe));

Étape	Lignes	Instruction	Effet	Écrit
1	2–3, 10	`dfs(0);`	`dfs(0)` marque Kaolack et l’ajoute au préfixe ; la pile d’appels contient `dfs(0)`. Les nombres en gras donnent l’ordre préfixe.
2	2–5	`dfs(1);`	Le premier voisin de Kaolack, 1 (Kaffrine), n’est pas marqué : `dfs(1)` le marque, avant d’examiner les autres voisins.
3	2–5	`dfs(2);`	Kaffrine examine 0 (marqué), puis 2 : `dfs(2)`, Tambacounda.
4	2–5	`dfs(3);`	Tambacounda examine 1 (marqué), puis 3 : `dfs(3)`, Kédougou. Le parcours s’enfonce.
5	4–5, 7	`postfixe.add(3);`	Kédougou n’a qu’un voisin, déjà marqué : `dfs(3)` se termine, 3 entre dans le postfixe et l’appel est dépilé. Retour dans `dfs(2)`.
6	2–5	`dfs(4);`	Tambacounda passe à son voisin suivant, 4 : `dfs(4)`, Vélingara.
7	2–5	`dfs(5);`	Vélingara examine 2 (marqué), puis 5 : `dfs(5)`, Kolda.
8	2–5	`dfs(6);`	Kolda examine 0 et 4 (marqués), puis 6 : `dfs(6)`, Sédhiou.
9	2–5	`dfs(7);`	Sédhiou examine 5 (marqué), puis 7 : `dfs(7)`, Ziguinchor. La pile contient 7 appels.
10	4–5, 7	`postfixe.add(7); postfixe.add(6);`	Les voisins de Ziguinchor (0, 5, 6) sont tous marqués : `dfs(7)` se termine, puis `dfs(6)` ; 7 et 6 entrent dans le postfixe.
11	4–5, 7	`postfixe.add(v); (5, 4, 2, 1, 0)`	En remontant, chaque appel trouve ses voisins restants marqués et se termine : 5, 4, 2, 1, puis 0. Les 7 arêtes rouges et foncées forment l’arbre de parcours.
12	11	`System.out.println(...prefixe...);`	L’ordre préfixe, celui des entrées dans `dfs` : chaque ville est visitée avant ses descendants.	`Kaolack Kaffrine Tambacounda Kedougou Velingara Kolda Sedhiou Ziguinchor`
13	12	`System.out.println(...postfixe...);`	L’ordre postfixe, celui des sorties : une ville n’y entre qu’après toutes celles atteintes depuis elle. Kaolack, la racine, sort en dernier.	`Kedougou Ziguinchor Sedhiou Kolda Velingara Tambacounda Kaffrine Kaolack`

L’appel dfs(0) part de Kaolack et descend aussitôt vers son premier voisin, Kaffrine, puis vers Tambacounda et Kédougou. Kédougou n’a qu’un voisin, déjà marqué : son appel se termine, Kédougou entre la première dans le postfixe, et l’exécution revient dans dfs(2), qui passe à son voisin suivant, Vélingara. Le parcours s’enfonce alors jusqu’à Ziguinchor par Kolda et Sédhiou : la pile compte sept appels. Tous les voisins de Ziguinchor sont marqués ; les appels se terminent l’un après l’autre en remontant la pile, et Kaolack, la racine, sort en dernier. L’arbre de parcours est très différent de celui de la largeur : une longue branche Kaolack–Kaffrine–Tambacounda–Vélingara–Kolda–Sédhiou–Ziguinchor.

Étape 5 : fin de dfs(3)

Étape 9 : dfs(7), sept appels en cours

Sortie \(\rightarrow\)

Kaolack Kaffrine Tambacounda Kedougou Velingara Kolda Sedhiou Ziguinchor
Kedougou Ziguinchor Sedhiou Kolda Velingara Tambacounda Kaffrine Kaolack

Une pile d’appels bornée

La récursion empile un appel par sommet de la branche en cours. Sur une chaîne de sommets reliés l’un au suivant, ParcoursProfondeur lève StackOverflowError dès quelques milliers de sommets (entre \(4\,000\) et \(6\,000\) sur la machine de mesure ; le seuil dépend de la taille de la pile de la machine virtuelle). On agrandit alors la pile (option -Xss de java : -Xss32m permet d’en parcourir \(100\,000\), comme pour les arbres dégénérés de la Séance 4) ou l’on écrit le parcours avec une pile explicite (ArrayDeque et push, pop). Le parcours en largeur n’a pas ce problème : sa file est un objet du tas mémoire.

Les deux parcours ont le même coût et atteignent les mêmes sommets ; ils diffèrent par l’ordre de visite, donc par ce qu’ils révèlent. La largeur donne les plus courts chemins en nombre d’arêtes. La profondeur donne les ordres préfixe et postfixe, sur lesquels reposent la détection de cycles et le tri topologique.

Le tri topologique

Un graphe orienté représente des contraintes d’ordre : un cours exige un autre cours, une tâche doit attendre la fin d’une autre, une classe Java se compile après celles qu’elle utilise. Le graphe suivant donne, en exemple, des prérequis entre huit cours : Algo (algorithmique), ProgC (programmation C), Maths (mathématiques discrètes), Java (programmation Java), BD (bases de données), SDA (structures de données), GL (génie logiciel) et IA (intelligence artificielle). Un arc \(v\to w\) signifie que \(v\) est un prérequis de \(w\).

Tri topologique

Un tri topologique d’un graphe orienté est un ordre de ses sommets dans lequel tout arc \(v\to w\) va d’un sommet vers un sommet placé après lui. Il en existe un si et seulement si le graphe est sans cycle (DAG) : sur un cycle, chaque sommet devrait précéder le suivant, et le dernier le premier.

L’algorithme tient en une phrase : faire un parcours en profondeur depuis chaque sommet non encore marqué, et ranger les sommets dans l’ordre postfixe inversé. Le code du cours empile chaque sommet à la sortie de son appel : la pile, lue du sommet vers le fond, donne l’ordre inversé, sans retournement.

Exemple pas à pas : les prérequis

static void dfs(int v) {
    marque[v] = true;
    for (int w : g.adj(v)) {
        if (!marque[w]) dfs(w);
    }
    ordre.push(v);
}
// dans main :
for (int v = 0; v < g.V(); v++) {
    if (!marque[v]) dfs(v);
}
System.out.println(noms(ordre));

Étape	Lignes	Instruction	Effet	Écrit
1	2, 9–10	`dfs(0);`	\(v=0\) : Algo n’est pas marqué, `dfs(0)` le marque. Ses successeurs sont 1 (ProgC) et 4 (BD).
2	2–4	`dfs(1);`	Le premier successeur, 1 (ProgC), n’est pas marqué : `dfs(1)`.
3	2–4	`dfs(3);`	ProgC a pour successeur 3 (Java) : `dfs(3)`.
4	2–4	`dfs(5);`	Java a pour successeurs 5 (SDA) et 6 (GL) ; le premier, 5, est appelé.
5	2–4, 6	`ordre.push(7);`	`dfs(7)` : IA, marqué, n’a aucun successeur, l’appel se termine et 7 est empilé en tête de `ordre`, le premier.
6	2–4, 6	`ordre.push(5); dfs(6); ordre.push(6);`	SDA se termine (5 en tête, devant 7) ; Java passe à 6 (GL), sans successeur, aussitôt empilé.
7	6	`ordre.push(3); ordre.push(1);`	Java puis ProgC se terminent : 3, puis 1, en tête. Chaque cours entre devant tous ceux qu’il précède.
8	2–4, 6	`dfs(4); ordre.push(4); ordre.push(0);`	Retour dans Algo : `dfs(4)`, BD, dont le successeur GL est déjà marqué ; BD, puis Algo, sont empilés.
9	2–4, 6, 9–10	`dfs(2); ordre.push(2);`	\(v=1\) est marqué ; \(v=2\), Maths, ne l’est pas : ses successeurs SDA et IA sont marqués, il est empilé en tête. Les sommets 3 à 7 sont marqués.
10	12	`System.out.println(...ordre...);`	L’ordre de la pile, du sommet vers le fond : l’ordre postfixe inversé. Chaque arc va d’un cours vers un cours placé après lui.	`Maths Algo BD ProgC Java GL SDA IA`

La boucle de main lance dfs(0) sur Algo. Le parcours descend vers ProgC, Java, SDA, puis IA, qui n’a aucun successeur : IA est empilé le premier, donc placé en dernier. SDA, puis GL (le second successeur de Java), puis Java et ProgC se terminent et passent devant. De retour dans Algo, dfs(4) traite BD, dont le seul successeur, GL, est déjà marqué ; BD puis Algo sont empilés. La boucle de main trouve enfin Maths, que rien n’a atteint : Maths est empilé en tête. L’ordre obtenu, Maths, Algo, BD, ProgC, Java, GL, SDA, IA, respecte les neuf arcs.

Étape 6 : SDA et GL terminés

Étape 9 : Maths, en tête

Sortie \(\rightarrow\)

Maths Algo BD ProgC Java GL SDA IA

Justesse de l’ordre postfixe inversé

Soit un arc \(v\to w\), examiné pendant l’appel dfs(v). Trois cas se présentent.

\(w\) n’est pas marqué : dfs(w) est appelé pendant dfs(v) et se termine avant lui.
\(w\) est marqué et son appel est terminé : \(w\) est déjà dans le postfixe, avant \(v\).
\(w\) est marqué et son appel est en cours : dfs(v) a été appelé, directement ou non, depuis dfs(w) ; il existe donc un chemin \(w\to\dots\to v\), et l’arc \(v\to w\) ferme un cycle.

Dans un DAG, le cas 3 est impossible ; dans les deux autres, \(w\) sort avant \(v\), et l’ordre postfixe inversé place \(v\) avant \(w\). Le cas 3 donne aussi un test de cycle : un arc vers un sommet dont l’appel est en cours. La classe CycleOriente tient un tableau surPile, vrai pendant l’appel dfs(v), et reconstruit le cycle en remontant edgeTo de \(v\) jusqu’à \(w\) (méthode remonte, non montrée).

private void dfs(Graphe g, int v) {
    marque[v] = true;
    surPile[v] = true;
    for (int w : g.adj(v)) {
        if (cycle != null) return;
        if (!marque[w]) {
            edgeTo[w] = v;
            dfs(g, w);
        } else if (surPile[w]) {  // arc vers la pile
            cycle = remonte(v, w);
        }
    }
    surPile[v] = false;
}

Graphe g = Reseau.prerequis();
CycleOriente c = new CycleOriente(g);
System.out.println(c.cycle());
g.addEdge(5, 1);  // SDA -> ProgC
c = new CycleOriente(g);
String s = Reseau.cours(c.cycle());
System.out.println(s);

Sortie \(\rightarrow\)

null
SDA ProgC Java SDA

Les prérequis du cours forment un DAG : aucun cycle (null). Un arc SDA\(\to\)ProgC, saisi par erreur, ferme le cycle SDA\(\to\)ProgC\(\to\)Java\(\to\)SDA : plus aucun ordre des cours ne respecte tous les prérequis. Le parcours qui le découvre coûte, lui aussi, \(\Theta(V+E)\).

Les plus courts chemins de Dijkstra

Le parcours en largeur trouve les chemins qui ont le moins d’arêtes. Sur un graphe pondéré, on cherche les chemins de plus petite longueur, la somme de leurs poids : le moins de kilomètres, de francs CFA ou de minutes. L’algorithme d’Edsger Dijkstra (1959) résout ce problème quand les poids sont positifs ou nuls.

Distance et relâchement

La distance \(d(s,v)\) est la plus petite longueur d’un chemin de \(s\) à \(v\). L’algorithme tient pour chaque sommet une distance provisoire distTo[v], longueur du meilleur chemin connu (\(\infty\) au départ, 0 pour \(s\)), et la dernière arête edgeTo[v] de ce chemin. Relâcher l’arête \(v\)–\(w\), c’est tester si passer par \(v\) améliore le chemin connu vers \(w\) : \[\text{si } \texttt{distTo[v]}+p(v,w)<\texttt{distTo[w]}~: \texttt{distTo[w]}\leftarrow\texttt{distTo[v]}+p(v,w)\ \text{ et }\ \texttt{edgeTo[w]}\leftarrow v\text{--}w.\]

Algorithme de Dijkstra

À chaque tour, extraire le sommet non définitif de plus petite distance provisoire, le déclarer définitif, et relâcher toutes ses arêtes. Une file de priorité (le tas de la Séance 4) donne ce sommet.

Le tas range des Entree, couples (sommet, distance) comparés par distance, puis par numéro de sommet à distance égale. La classe BinaryMinHeap de la Séance 4 n’a pas d’opération qui diminue la clé d’une entrée déjà rangée : quand un relâchement améliore distTo[w], on insère une nouvelle entrée pour \(w\), et l’ancienne reste dans le tas. Quand elle en sort, son sommet est déjà définitif : l’entrée est périmée, et la ligne if (fait[v]) continue; l’ignore. Sedgewick et Wayne (§ 4.4) utilisent à la place un tas indexé (IndexMinPQ), qui remplace l’entrée ; le résultat est le même.

private void relacher(Arete e, int v) {
    int w = e.autre(v);
    if (distTo[v] + e.poids < distTo[w]) {  // meilleur chemin par v
        distTo[w] = distTo[v] + e.poids;
        edgeTo[w] = e;
        tas.insert(new Entree(w, distTo[w]));
        insertions++;
    }
}

Exemple pas à pas : le réseau depuis Kaolack

Le programme suivant est le cœur de la classe Dijkstra ; distTo vaut Integer.MAX_VALUE (\(\infty\)) pour tous les sommets avant la ligne 2, et relacher est la méthode ci-dessus. Il écrit la distance de chaque sommet au moment où il devient définitif, puis le tableau des distances.

var tas = new BinaryMinHeap<Entree>();
distTo[0] = 0;
tas.insert(new Entree(0, 0));
while (!tas.isEmpty()) {
    int v = tas.extractMin().sommet;
    if (fait[v]) continue;
    fait[v] = true;
    System.out.print(distTo[v] + " ");
    for (Arete e : g.adj(v)) relacher(e, v);
}
System.out.println(Arrays.toString(distTo));

Étape	Lignes	Instruction	Effet	Écrit
1	1–3	`tas.insert(new Entree(0, 0));`	`distTo` vaut \(\infty\), sauf `distTo[0]` = 0 ; le tas reçoit `0:0`.
2	5–9	`int v = tas.extractMin().sommet;`	Kaolack sort ; Kaffrine reçoit 63, Ziguinchor 251, Kolda 272.	`0`
3	5–9	`int v = tas.extractMin().sommet;`	Kaffrine sort à 63 ; Tambacounda reçoit 273. Trait épais foncé : les arêtes `edgeTo`.	`63`
4	5–9	`int v = tas.extractMin().sommet;`	Ziguinchor sort à 251 ; Sédhiou reçoit 414, Kolda reste à 272.	`251`
5	5–9	`int v = tas.extractMin().sommet;`	Kolda sort à 272 ; Sédhiou passe à 357, Vélingara reçoit 395.	`272`
6	5–9	`int v = tas.extractMin().sommet;`	Tambacounda sort (273) ; Kédougou reçoit 506, Vélingara 376.	`273`
7	5–9	`int v = tas.extractMin().sommet;`	Sédhiou sort à 357, définitif ; aucune distance n’est améliorée.	`357`
8	5–9	`int v = tas.extractMin().sommet;`	Vélingara sort à 376, définitif ; aucune distance n’est améliorée.	`376`
9	5–6	`if (fait[v]) continue;`	`395:4` sort, mais Vélingara est déjà définitif : entrée périmée.
10	5–6	`if (fait[v]) continue;`	`414:6` sort, mais Sédhiou est déjà définitif : entrée périmée.
11	5–9	`int v = tas.extractMin().sommet;`	Kédougou sort à 506, définitif ; aucune distance n’est améliorée.	`506`
12	11	`System.out.println(Arrays.toString(distTo));`	Distances définitives ; en foncé, l’arbre des plus courts chemins.	`[0, 63, 273, 506, 376, 272, 357, 251]`

Kaolack sort la première et donne leurs premières distances à ses trois voisins : 63, 251 et 272. Kaffrine (63) sort ensuite, et Tambacounda reçoit \(63+210=273\). Ziguinchor (251) donne 414 à Sédhiou ; par Ziguinchor, Kolda coûterait \(251+188=439\), plus que 272 : rien ne change. Quand Kolda sort (272), deux relâchements améliorent : Sédhiou passe de 414 à \(272+85=357\), et Vélingara reçoit 395. Tambacounda (273) améliore à son tour Vélingara, de 395 à \(273+103=376\), et donne 506 à Kédougou. Deux entrées sont devenues périmées, 414:6 et 395:4 : elles sortent du tas après leur sommet et sont ignorées (étapes 9 et 10). Les distances écrites ligne 8 croissent : 0, 63, 251, 272, 273, 357, 376, 506.

Étape 5 : Kolda sort, deux améliorations

Étape 6 : Tambacounda sort

Sortie \(\rightarrow\)

0 63 251 272 273 357 376 506 
[0, 63, 273, 506, 376, 272, 357, 251]

La classe Dijkstra remonte un chemin par edgeTo, comme ParcoursLargeur, mais d’arête en arête :

public List<Integer> chemin(int v) {
    if (distTo[v] == Integer.MAX_VALUE) return null;
    LinkedList<Integer> c = new LinkedList<>();
    for (int x = v; x != s; x = edgeTo[x].autre(x)) c.addFirst(x);
    c.addFirst(s);
    return c;
}
// dans main :
String[] nom = Reseau.VILLES;
Dijkstra d = new Dijkstra(Reseau.routesKm(), 0);
System.out.println(d.distance(4) + " km : " + Reseau.noms(d.chemin(4), nom));
System.out.println(d.extractions + " " + d.perimees + " " + d.insertions);

Sortie \(\rightarrow\)

376 km : Kaolack Kaffrine Tambacounda Velingara
10 2 10

Le plus court chemin de Kaolack à Vélingara mesure 376 km et passe par Kaffrine et Tambacounda, alors que le parcours en largeur passait par Kolda. Les compteurs donnent 10 extractions (8 sommets et 2 entrées périmées) et 10 insertions.

Justesse et coût de Dijkstra

Invariant : quand \(v\) sort du tas, \(\texttt{distTo[v]}=d(s,v)\). Supposons un chemin plus court \(P\) de \(s\) à \(v\). Il part de \(s\), définitif, et finit en \(v\), qui ne l’est pas encore : il quitte l’ensemble des sommets définitifs par une arête \(x\)–\(u\), avec \(x\) définitif et \(u\) non définitif. Quand \(x\) est devenu définitif, l’arête \(x\)–\(u\) a été relâchée : distTo[u] est au plus la longueur de \(P\) jusqu’à \(u\). Comme \(v\) sort avant \(u\), \(\texttt{distTo[v]}\leq\texttt{distTo[u]}\) ; et la suite de \(P\), de \(u\) à \(v\), a une longueur positive ou nulle. Donc \(\texttt{distTo[v]}\leq\) longueur de \(P\) : \(P\) n’est pas plus court.

Coût : chaque relâchement réussi insère une entrée ; il y en a au plus \(E+1\) (une arête n’améliore qu’une fois en direction de son extrémité non définitive). Chaque entrée est insérée puis extraite en \(\mathcal{O}(\log E)=\mathcal{O}(\log V)\), puisque \(E<V^2\) ; chaque liste est lue une fois. Le total est \(\mathcal{O}((V+E)\log V)\).

Exemple pas à pas : un poids négatif

L’invariant utilise le fait que la suite d’un chemin a une longueur positive ou nulle. Le programme suivant exécute le même code sur quatre sommets reliés par des arcs, dont l’arc \(2\to1\) de poids \(-3\).

var tas = new BinaryMinHeap<Entree>();
distTo[0] = 0;
tas.insert(new Entree(0, 0));
while (!tas.isEmpty()) {
    int v = tas.extractMin().sommet;
    if (fait[v]) continue;
    fait[v] = true;
    System.out.print(distTo[v] + " ");
    for (Arete e : g.adj(v)) relacher(e, v);
}
System.out.println(Arrays.toString(distTo));

Étape	Lignes	Instruction	Effet	Écrit
1	1–3	`tas.insert(new Entree(0, 0));`	Le même code, sur quatre sommets reliés par des arcs ; l’arc \(2\to1\) pèse \(-3\).
2	5–9	`int v = tas.extractMin().sommet;`	0 sort à 0 : le sommet 1 reçoit 2, le sommet 2 reçoit 4.	`0`
3	5–9	`int v = tas.extractMin().sommet;`	1 sort à 2 et devient définitif : le sommet 3 reçoit \(2+2=4\).	`2`
4	5–9	`int v = tas.extractMin().sommet;`	2 sort à 4 (égalité avec 3 : le plus petit numéro d’abord) ; l’arc \(2\to1\) donne \(4-3=1<2\) : `distTo[1]` passe à 1, bien que 1 soit définitif.	`4`
5	5–6	`if (fait[v]) continue;`	L’entrée `1:1` sort, mais le sommet 1 est déjà définitif : elle est ignorée, et sa nouvelle distance n’est jamais propagée au sommet 3.
6	5–9	`int v = tas.extractMin().sommet;`	3 sort à 4, distance calculée depuis l’ancienne distance du sommet 1.	`4`
7	11	`System.out.println(Arrays.toString(distTo));`	`[0, 1, 4, 4]` : le chemin \(0\to2\to1\to3\) coûte \(4-3+2=3\), et `distTo[3]` vaut 4. Avec un poids négatif, un sommet extrait n’a pas forcément sa distance définitive.	`[0, 1, 4, 4]`

Le sommet 1 sort à l’étape 3 avec la distance 2 et devient définitif ; le sommet 3 reçoit \(2+2=4\). Quand le sommet 2 sort à son tour (4, à égalité avec le sommet 3, mais de plus petit numéro), l’arc \(2\to1\) donne \(4-3=1<2\) : distTo[1] passe à 1, alors que le sommet 1 était déclaré définitif. La nouvelle entrée 1:1 est ignorée à sa sortie, et la distance du sommet 3 n’est jamais recalculée : le programme écrit 4, alors que le chemin \(0\to2\to1\to3\) mesure \(4-3+2=3\).

Étape 4 : l’arc \(2\to1\) améliore le sommet 1, définitif

Étape 7 : distTo[3] reste à 4

Sortie \(\rightarrow\)

0 2 4 4 
[0, 1, 4, 4]

Poids négatifs

Avec un poids négatif, un sommet extrait n’a pas forcément sa distance définitive, et ses successeurs gardent une distance fausse. L’algorithme de Bellman-Ford (CLRS, § 22.1) traite les poids négatifs, en \(\mathcal{O}(VE)\), et détecte les cycles de longueur négative. Ajouter une constante à tous les poids pour les rendre positifs ne convient pas : un chemin de \(k\) arêtes est alors allongé de \(k\) fois la constante, et les chemins courts en arêtes sont avantagés.

Le coût mesuré

Le programme MesuresS5 exécute la classe Dijkstra sur des graphes connexes au hasard (anneau et cordes distinctes, \(E=4V\), poids de 1 à \(1\,000\), Random(2026)), de \(V=1\,000\) à \(64\,000\), et compte les comparaisons faites par le tas.

Les comparaisons restent entre \(0{,}64\) et \(0{,}68\) fois \((V+E)\log_2V\) sur toute la plage : le coût suit la borne à un facteur constant près. Moins de la moitié des arêtes améliorent une distance : \(1\,848\) entrées insérées pour \(4\,000\) arêtes à \(V=1\,000\), et le rapport reste vers \(0{,}45\). Parmi les \(1\,848\) extractions, \(1\,000\) rendent un sommet définitif et 848 sont des entrées périmées.

L’arbre couvrant minimal de Kruskal

On veut relier les huit villes par de la fibre optique, posée le long des routes, en utilisant le moins de câble possible. Le réseau obtenu doit relier toutes les villes ; il n’a aucune raison de contenir un cycle, puisqu’en retirer une arête laisserait les villes reliées avec moins de câble.

Arbre couvrant minimal

Dans un graphe connexe, pondéré et non orienté, un arbre couvrant est un ensemble de \(V-1\) arêtes qui relie tous les sommets sans former de cycle. Un arbre couvrant de poids minimal (minimum spanning tree), dit plus brièvement arbre couvrant minimal, est un arbre couvrant dont la somme des poids est la plus petite.

Propriété de la coupe

Partageons les sommets en deux groupes non vides ; une arête qui relie les deux groupes traverse la coupe. L’arête la plus légère qui traverse une coupe appartient à un arbre couvrant minimal. En effet, soit \(T\) un arbre couvrant minimal qui ne la contient pas : l’ajouter à \(T\) crée un cycle, qui traverse la coupe une seconde fois par une autre arête, au moins aussi lourde. Échanger les deux donne un arbre couvrant de poids au plus égal : il est minimal, et il contient l’arête.

L’algorithme de Joseph Kruskal (1956) examine les arêtes par poids croissant et garde chacune qui ne ferme pas de cycle avec les arêtes déjà gardées. Les arêtes gardées forment une forêt, dont les arbres grossissent et se rejoignent. Quand l’arête \(v\)–\(w\) est gardée, \(v\) et \(w\) sont dans deux arbres différents ; toutes les arêtes plus légères ont déjà été examinées, gardées ou rejetées : \(v\)–\(w\) est donc la plus légère qui traverse la coupe entre l’arbre de \(v\) et le reste, et la propriété de la coupe garantit le résultat. Le code du cours range les arêtes dans le tas de la Séance 4 (Arete est comparée par poids, puis par extrémités).

Exemple pas à pas : la fibre optique entre les huit villes

Le test de cycle est une méthode relies(foret, v, w), qui lance un parcours en largeur dans la forêt construite et répond si \(w\) est atteint depuis \(v\).

var tas = new BinaryMinHeap<Arete>();
for (Arete e : g.aretes()) tas.insert(e);
Graphe foret = new Graphe(g.V(), false);
while (arbre.size() < g.V() - 1) {
    Arete e = tas.extractMin();
    if (relies(foret, e.v, e.w)) continue;
    arbre.add(e);
    foret.addEdge(e.v, e.w);
    poids += e.poids;
    System.out.print(e.poids + " ");
}
System.out.println("total " + poids);

Étape	Lignes	Instruction	Effet	Écrit
1	1–3	`for (Arete e : g.aretes()) tas.insert(e);`	Les 10 arêtes entrent dans un tas rangé par poids ; forêt vide.
2	5–10	`Arete e = tas.extractMin();`	Kaolack–Kaffrine (63 km) sort ; `relies(foret, 0, 1)` est faux : retenue.	`63`
3	5–10	`Arete e = tas.extractMin();`	Kolda–Sédhiou (85 km) sort ; villes non reliées : retenue.	`85`
4	5–10	`Arete e = tas.extractMin();`	Tambacounda–Vélingara (103 km) sort ; villes non reliées : retenue.	`103`
5	5–10	`Arete e = tas.extractMin();`	Vélingara–Kolda (123 km) sort ; villes non reliées : retenue.	`123`
6	5–10	`Arete e = tas.extractMin();`	Sédhiou–Ziguinchor (163 km) sort ; villes non reliées : retenue.	`163`
7	5–6	`if (relies(foret, e.v, e.w)) continue;`	Kolda–Ziguinchor (188 km) sort ; déjà reliées par Sédhiou : rejetée.
8	5–10	`Arete e = tas.extractMin();`	Kaffrine–Tambacounda (210 km) sort ; villes non reliées : retenue.	`210`
9	5–10	`Arete e = tas.extractMin();`	Tambacounda–Kédougou (233 km) retenue : 7 arêtes, \(V-1\), fin.	`233`
10	12	`System.out.println("total " + poids);`	980 km relient les huit villes ; aucun arbre couvrant n’est plus court.	`total 980`

Les cinq arêtes les plus légères, de 63 à 163 km, sont gardées : aucune ne relie deux villes déjà reliées. L’arête Kolda–Ziguinchor (188 km) sort ensuite, mais la forêt relie déjà ces deux villes par Sédhiou (\(85+163\) km) : elle fermerait un cycle, elle est rejetée. Kaffrine–Tambacounda (210 km) relie les deux morceaux de la forêt, et Tambacounda–Kédougou (233 km) rattache la dernière ville : 7 arêtes, \(V-1\), la boucle s’arrête. Les arêtes de 251 et 272 km ne sortent jamais du tas. L’arbre mesure 980 km, sur les \(1\,691\) km de routes.

Étape 7 : 188 km, rejetée

Étape 9 : 233 km, la dernière

Sortie \(\rightarrow\)

63 85 103 123 163 210 233 
total 980

Le test de cycle et son coût

private boolean relies(Graphe foret, int v, int w) {
    ParcoursLargeur p = new ParcoursLargeur(foret, v);
    visites += p.atteints;
    return p.atteint(w);  // un chemin v ... w existe deja
}

Random r = new Random(221);
for (int V : new int[] {500, 1000, 2000, 4000}) {
    GraphePondere g = new GraphePondere(V, false);
    for (int[] a : Generateur.aretes(V, 4 * V, r)) g.addEdge(a[0], a[1], a[2]);
    Kruskal k = new Kruskal(g);
    System.out.printf(Locale.ROOT, "%5d : %6d examinees, %6d rejets, "
        + "%9d visites, %.3f V^2%n", V, k.examinees, k.rejets,
        k.visites, k.visites / ((double) V * V));
}

Sortie \(\rightarrow\)

  500 :   1718 examinees,   1219 rejets,    611838 visites, 2.447 V^2
 1000 :   2971 examinees,   1972 rejets,   1986671 visites, 1.987 V^2
 2000 :   5681 examinees,   3682 rejets,   7389527 visites, 1.847 V^2
 4000 :  13589 examinees,   9590 rejets,  38476757 visites, 2.405 V^2

Chaque test parcourt la composante de \(v\) dans la forêt, jusqu’à \(V\) sommets, et alloue trois tableaux de \(V\) cases. Les visites restent vers \(2V^2\) (de \(1{,}85\) à \(2{,}45\,V^2\)) : quand \(V\) double, elles sont multipliées par 3 à 5, et Kruskal coûte ici \(\mathcal{O}(EV)\). C’est le choix de cette séance : un test de cycle par un parcours déjà connu. La Séance 6 le remplace par la structure Union-Find, qui répond à « \(v\) et \(w\) sont-ils dans le même arbre ? » et réunit deux arbres en un temps presque constant : Kruskal coûte alors \(\mathcal{O}(E\log E)\), le coût du tri des arêtes par le tas.

Les algorithmes côte à côte

question	algorithme	structure	coût	sur le réseau du cours
moins d’arêtes	largeur	file	\(\Theta(V+E)\)	Kédougou à 3 tronçons
ordres, cycles	profondeur	pile d’appels	\(\Theta(V+E)\)	préfixe, postfixe
ordre des prérequis	postfixe inversé	pile	\(\Theta(V+E)\)	8 cours ordonnés
plus courts en km	Dijkstra	tas	\(\mathcal{O}((V+E)\log V)\)	Vélingara à 376 km
arbre couvrant minimal	Kruskal	tas, test de cycle	\(\mathcal{O}(EV)\) ici	980 km

Tous ces algorithmes travaillent sur les listes d’adjacence. Les deux premiers ne regardent pas les poids ; Dijkstra suppose des poids positifs ou nuls ; Kruskal suppose un graphe non orienté et connexe (sur un graphe non connexe, il donne une forêt couvrante). L’arbre des plus courts chemins de Dijkstra et l’arbre couvrant minimal de Kruskal sont deux arbres différents, qui répondent à deux questions différentes : le premier minimise la distance de chaque ville à Kaolack, le second la longueur totale du réseau.

Exercices corrigés

Les trois exercices suivants reprennent les mécanismes de la séance sous la forme demandée en TD : un tableau à remplir, tour par tour. Chaque correction donne la règle appliquée, chaque étape, l’état final et l’erreur fréquente à éviter.

Exercice 1 : les deux parcours d’un même graphe

Un graphe non orienté a sept sommets, A à G (numéros 0 à 6), et neuf arêtes, ajoutées dans cet ordre : A–B, A–D, B–C, B–E, C–F, D–E, E–F, E–G, F–G.

Écrire les listes d’adjacence (ajout en queue).
Dérouler le parcours en largeur depuis A : à chaque tour, le sommet qui sort, les sommets marqués et la file après le tour. Donner distTo et l’arbre de parcours.
Dérouler le parcours en profondeur depuis A : les entrées et sorties d’appels, la pile, les ordres préfixe et postfixe, et l’arbre de parcours.

Correction

(a) Règle : chaque arête \(v\)–\(w\) ajoute \(w\) en queue de la liste de \(v\), et \(v\) en queue de celle de \(w\). A : B, D ; B : A, C, E ; C : B, F ; D : A, E ; E : B, D, F, G ; F : C, E, G ; G : E, F. Les degrés totalisent \(2+3+2+2+4+3+2=18=2\times9\).

(b) Règle : retirer le sommet de tête ; marquer et mettre en queue, dans l’ordre de sa liste, chaque voisin non marqué, à distance \(+1\).

tour	sort	marqués (distance)	file après le tour
1	A	B (1), D (1)	B, D
2	B	C (2), E (2)	D, C, E
3	D	— (A et E déjà marqués)	C, E
4	C	F (3)	E, F
5	E	G (3) ; F déjà marqué	F, G
6	F	—	G
7	G	—	vide

distTo : A 0, B 1, C 2, D 1, E 2, F 3, G 3. L’arbre de parcours a les arêtes A–B, A–D, B–C, B–E, C–F, E–G ; les 18 entrées des listes ont été lues une fois chacune.

(c) Règle : dfs(v) marque \(v\) (préfixe), appelle dfs sur chaque voisin non marqué, dans l’ordre de la liste, puis range \(v\) dans le postfixe.

événement	pile d’appels	raison
entrée A, B, C, F, E, D	A B C F E D	premier voisin libre à chaque fois (E : B marqué, D libre)
sortie D	A B C F E	voisins de D : A, E, marqués
entrée G, sortie G	A B C F E	voisin suivant de E : G ; ceux de G sont marqués
sorties E, F, C, B, A	vide	tous les voisins restants sont marqués

Préfixe : A, B, C, F, E, D, G ; postfixe : D, G, E, F, C, B, A. L’arbre de parcours (rangs préfixe en orange) est A–B, B–C, C–F, F–E, E–D, E–G : une longue branche, de hauteur 5, quand la largeur donnait un arbre de hauteur 3.

Erreur fréquente : en largeur, marquer un sommet quand il sort de la file au lieu de quand il y entre. E serait alors mis en file deux fois (par B, puis par D), et sa distance pourrait être écrasée ; la règle « marquer à l’entrée » garantit une seule entrée par sommet.

Exercice 2 : l’algorithme de Dijkstra

Un graphe non orienté pondéré a six sommets, A à F, et huit arêtes : A–B 3, A–C 1, C–B 2, B–D 4, C–E 7, D–E 2, D–F 6, E–F 1.

Dérouler l’algorithme de Dijkstra depuis A : à chaque tour, l’entrée extraite, les relâchements qui améliorent une distance, distTo et le contenu du tas.
Quelles entrées sont périmées ? Combien y a-t-il d’extractions et d’insertions ?
Donner l’arbre des plus courts chemins et le chemin de A à F.

Correction

(a) Règle : extraire la plus petite entrée ; si son sommet est déjà définitif, l’ignorer ; sinon, le déclarer définitif et relâcher ses arêtes, en insérant une entrée pour chaque distance améliorée (strictement plus petite).

extrait	relâchements qui améliorent	A	B	C	D	E	F	tas après
A (0)	B : 3 ; C : 1	0	3	1	\(\infty\)	\(\infty\)	\(\infty\)	`1:C`, `3:B`
C (1)	E : \(1+7=8\) (B : \(1+2=3\), pas \(<3\))	0	3	1	\(\infty\)	8	\(\infty\)	`3:B`, `8:E`
B (3)	D : \(3+4=7\)	0	3	1	7	8	\(\infty\)	`7:D`, `8:E`
D (7)	F : \(7+6=13\) (E : \(7+2=9\), pas \(<8\))	0	3	1	7	8	13	`8:E`, `13:F`
E (8)	F : \(8+1=9<13\)	0	3	1	7	8	9	`9:F`, `13:F`
F (9)	---	0	3	1	7	8	9	`13:F`
F (13)	périmée, ignorée	inchangé						vide

(b) Une entrée périmée, 13:F, posée par D puis rendue inutile quand E a amélioré F à 9. 7 extractions (6 sommets et 1 entrée périmée) et 7 insertions (la source et 6 relâchements réussis).

(c) edgeTo : B par A–B, C par A–C, D par B–D, E par C–E, F par E–F. Le chemin de A à F est A, C, E, F, de longueur \(1+7+1=9\) ; l’arbre pèse \(3+1+4+7+1=16\).

Erreur fréquente : déclarer un sommet définitif quand il reçoit sa première distance, au lieu de quand il sort du tas. F serait alors fixé à 13, la valeur posée par D, alors que le chemin par E mesure 9. Une autre erreur consiste à relâcher avec \(\leq\) : à égalité (B par C, \(1+2=3\)), la distance ne change pas, et l’entrée insérée serait inutile.

Exercice 3 : l’algorithme de Kruskal sur le même graphe

Ranger les arêtes par poids croissant (à poids égal, comme compareTo de Arete : plus petite première extrémité, puis plus petite seconde, les extrémités étant prises dans l’ordre de l’énoncé). Pour chaque arête examinée, dire si elle est gardée ou rejetée, et pourquoi.
Donner l’arbre couvrant minimal et son poids ; quelles arêtes ne sont jamais examinées ?
Comparer avec l’arbre des plus courts chemins de l’exercice 2.

Correction

(a) Règle : une arête est rejetée si et seulement si ses deux extrémités sont déjà dans le même arbre de la forêt ; la boucle s’arrête à \(V-1=5\) arêtes gardées.

arête	poids	décision	arbres de la forêt après
A--C	1	gardée	{A, C}
E--F	1	gardée (A--C passe avant : \(0<4\))	{A, C}, {E, F}
C--B	2	gardée	{A, B, C}, {E, F}
D--E	2	gardée	{A, B, C}, {D, E, F}
A--B	3	rejetée : A et B sont reliés par C	inchangé
B--D	4	gardée : les deux arbres se rejoignent	{A, B, C, D, E, F}

(b) L’arbre couvrant minimal a les arêtes A–C, E–F, C–B, D–E, B–D, de poids \(1+1+2+2+4=10\), sur les 26 du graphe. D–F (6) et C–E (7) ne sortent jamais du tas.

(c) L’arbre des plus courts chemins depuis A pèse 16 : il utilise A–B (3) et C–E (7), qui ne sont pas dans l’arbre couvrant minimal. Inversement, l’arbre couvrant minimal relie A à F par A, C, B, D, E, F, un chemin de longueur \(1+2+4+2+1=10\), plus long que les 9 de Dijkstra. Les deux arbres répondent à deux questions différentes.

Erreur fréquente : rejeter B–D parce que B et D « sont déjà dans l’arbre ». Ils sont bien touchés par des arêtes gardées, mais dans deux arbres différents de la forêt : B–D les réunit, sans cycle. Le test porte sur l’existence d’un chemin entre les deux extrémités, pas sur leur présence dans la forêt.

À retenir

Un graphe \(G=(V,E)\) est orienté ou non, pondéré ou non ; \(\sum_v\deg(v)=2|E|\). Un arbre est connexe, sans cycle, à \(V-1\) arêtes.
La matrice d’adjacence coûte \(\Theta(V^2)\) et teste une arête en \(\Theta(1)\) ; les listes coûtent \(\Theta(V+E)\) et donnent les voisins de \(v\) en \(\Theta(\deg v)\) : c’est le choix des graphes creux.
Le parcours en largeur utilise une file ; distTo est le plus petit nombre d’arêtes depuis la source, edgeTo l’arbre de parcours ; \(\Theta(V+E)\).
Le parcours en profondeur utilise la pile des appels ; il donne les ordres préfixe et postfixe ; \(\Theta(V+E)\).
L’ordre postfixe inversé d’un DAG est un tri topologique ; un arc vers un sommet dont l’appel est en cours révèle un cycle.
Dijkstra extrait du tas le sommet le plus proche, le rend définitif et relâche ses arêtes ; il exige des poids positifs ou nuls et coûte \(\mathcal{O}((V+E)\log V)\).
Kruskal examine les arêtes par poids croissant et rejette celles qui ferment un cycle ; la propriété de la coupe garantit un arbre couvrant minimal.

Prochaine séance

La Séance 6 traite les ensembles disjoints (Union-Find : QuickFind, QuickUnion, union pondérée, compression de chemin), qui donnent à Kruskal un test de cycle presque constant, puis les tris par insertion, par fusion et rapide, et la borne \(\Omega(n\log n)\) des tris par comparaison. D’ici là, le TD de la Séance 5 reprend les traces de ce document sur d’autres graphes, et le TP fait écrire, tester et mesurer les classes du cours.

Références

Sedgewick, Wayne — Algorithms, 4^e éd., Addison-Wesley, 2011 (§ 4.1 : graphes non orientés, parcours ; § 4.2 : graphes orientés, cycles, tri topologique ; § 4.3 : arbres couvrants minimaux ; § 4.4 : plus courts chemins).
Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4^e éd., MIT Press, 2022 (ch. 20 : algorithmes élémentaires sur les graphes ; ch. 21 : arbres couvrants minimaux ; ch. 22 : plus courts chemins à source unique).
Skiena — The Algorithm Design Manual, 3^e éd., Springer, 2020 (ch. 7 : parcours de graphes ; ch. 8 : graphes pondérés).
Dijkstra — « A note on two problems in connexion with graphs », Numerische Mathematik, 1, 1959.
Kruskal — « On the shortest spanning subtree of a graph and the traveling salesman problem », Proceedings of the American Mathematical Society, 7(1), 1956.
Logistics Cluster — Logistics Capacity Assessment, Senegal, § 2.3 : réseau routier (distances entre villes).

Modéliser des relations

Représenter un graphe

Exemple pas à pas : la construction des listes

Les coûts des deux représentations

Le parcours en largeur

Exemple pas à pas : le réseau depuis Kaolack

Le chemin le plus court en tronçons

Le parcours en profondeur

Exemple pas à pas : le réseau depuis Kaolack

Le tri topologique

Exemple pas à pas : les prérequis

Justesse de l’ordre postfixe inversé

Les plus courts chemins de Dijkstra

Exemple pas à pas : le réseau depuis Kaolack

Exemple pas à pas : un poids négatif

Le coût mesuré

L’arbre couvrant minimal de Kruskal

Exemple pas à pas : la fibre optique entre les huit villes

Le test de cycle et son coût

Les algorithmes côte à côte

Exercices corrigés

Exercice 1 : les deux parcours d’un même graphe

Exercice 2 : l’algorithme de Dijkstra

Exercice 3 : l’algorithme de Kruskal sur le même graphe

À retenir

Prochaine séance

Références

Pour cette séance