Chapitre 1 · 5 h
Graphes
Matrice et listes d'adjacence, parcours en profondeur et en largeur, connexité, détection de cycle, plus court chemin en nombre d'arêtes, Dijkstra en introduction.
Combien de correspondances au minimum entre deux stations de métro ? Un ami commun existe-t-il entre deux personnes d'un réseau social ? Quelles pages web sont atteignables depuis celle-ci ? Ces trois questions n'ont ni hiérarchie ni ordre : elles portent sur des objets reliés arbitrairement, et aucune structure vue jusqu'ici ne les modélise.
Le graphe est cet objet, et il généralise tout le semestre. Une liste est un graphe où chaque sommet a un successeur ; un arbre, un graphe sans cycle avec une racine. Retirer ces contraintes ouvre un champ immense — et introduit une difficulté nouvelle : on peut revenir sur ses pas.
Vocabulaire
Un graphe est un ensemble de sommets et un ensemble d'arêtes reliant des paires de sommets.
Il est orienté quand les liens ont un sens — on parle alors d'arcs : les liens hypertexte, les dépendances entre tâches, les relations « suit » d'un réseau social. Il est non orienté quand ils n'en ont pas : un réseau routier, une amitié réciproque.
Il est pondéré quand chaque arête porte un nombre — distance, durée, coût, capacité. C'est ce qui distinguera le chapitre en deux moitiés : sans poids, la longueur d'un chemin est son nombre d'arêtes ; avec poids, c'est la somme.
| Terme | Définition |
|---|---|
| Degré d'un sommet | nombre d'arêtes qui y aboutissent |
| Chemin | suite de sommets reliés deux à deux |
| Cycle | chemin qui revient à son point de départ |
| Connexe | tout sommet est atteignable depuis tout autre |
| Composante connexe | morceau maximal connexe d'un graphe qui ne l'est pas |
| Acyclique | sans aucun cycle |
Deux notations utiles : pour le nombre de sommets, pour le nombre d'arêtes. Un graphe est dit dense quand approche — presque tout est relié — et creux quand est de l'ordre de . Cette distinction décide de la représentation.
Deux représentations
La matrice d'adjacence est un tableau où la case vaut 1 s'il existe une arête de vers — ou le poids, s'il y en a un.
A B C D A ── B A 0 1 1 0 │ │ B 1 0 1 0 C ───┘ C 1 1 0 1 │ D 0 0 1 0 DTester l'existence d'une arête est en , ce qui est imbattable. Mais la mémoire est quel que soit le nombre d'arêtes, et surtout, énumérer les voisins d'un sommet demande de parcourir toute une ligne, soit — même s'il n'a que deux voisins.
Les listes d'adjacence associent à chaque sommet la liste de ses voisins.
A : B, CB : A, CC : A, B, DD : CLa mémoire est , et énumérer les voisins d'un sommet coûte exactement son degré. En revanche, tester une arête précise demande de parcourir une liste.
| Matrice | Listes | |
|---|---|---|
| Mémoire | ||
| Tester une arête | ||
| Énumérer les voisins |
Le choix se tranche par la densité, et par ce que fait l'algorithme. Les parcours de ce chapitre énumèrent les voisins en boucle et ne testent presque jamais une arête isolée : sur un graphe creux, les listes d'adjacence sont donc le bon choix — et les graphes réels sont massivement creux. Un réseau social de dix millions de comptes n'a pas relations ; il en a peut-être un milliard, et la matrice serait de toute façon impossible à loger.
Parcourir : la difficulté nouvelle
Les parcours du chapitre 7 se transposent presque tels quels — avec une modification qui n'est pas optionnelle.
Dans un arbre, on ne peut pas revenir sur un nœud déjà visité : il n'y a qu'un chemin depuis la racine. Dans un graphe, un cycle ramène sur ses pas, et un parcours naïf boucle indéfiniment. Il faut donc marquer les sommets visités, et tester ce marquage avant chaque descente. C'est la seule différence de fond avec le chapitre 7, et c'est l'oubli qui produit les boucles infinies du TD.
Le parcours en profondeur (DFS) s'enfonce aussi loin que possible avant de revenir en arrière. Il s'écrit récursivement en cinq lignes — la pile d'appels du bloc I fait le travail — ou itérativement avec une pile explicite.
fonction profondeur(s) marquer s traiter s pour chaque voisin v de s si v n'est pas marqué alors profondeur(v)Le parcours en largeur (BFS) explore par couches : d'abord les voisins immédiats, puis leurs voisins, et ainsi de suite. Il emploie une file, exactement comme au chapitre 7.
fonction largeur(s) marquer s ; enfiler s tant que la file n'est pas vide u ← défiler traiter u pour chaque voisin v de u non marqué marquer v ; enfiler vUn détail qui compte : on marque à l'enfilement, pas au défilement. Sinon un sommet accessible par deux chemins serait enfilé deux fois.
Les deux parcours coûtent avec des listes d'adjacence : chaque sommet est traité une fois, chaque arête examinée une fois (deux en non orienté).
Ce qu'un parcours résout
La connexité et les composantes. Un parcours depuis un sommet atteint exactement sa composante connexe. Pour toutes les trouver, on relance un parcours depuis chaque sommet non encore marqué, en comptant les relances : c'est le nombre de composantes, obtenu en .
La détection de cycle. En non orienté, un cycle existe si le parcours rencontre un sommet déjà marqué qui n'est pas le père immédiat — la nuance est essentielle, sans quoi toute arête serait vue comme un cycle. En orienté, c'est plus subtil : il faut repérer un arc vers un sommet encore en cours de traitement dans la pile de récursion, et non simplement déjà visité.
Le plus court chemin en nombre d'arêtes. C'est la propriété remarquable du BFS : il donne le plus court chemin, sans effort supplémentaire. La raison tient à l'ordre de visite — il explore tous les sommets à distance 1, puis tous ceux à distance 2, et ainsi de suite. Quand il atteint un sommet pour la première fois, il l'a donc fait par le chemin le plus court, et il suffit de mémoriser le prédécesseur pour reconstituer l'itinéraire. C'est la réponse à la question des correspondances de métro — à condition que toutes les arêtes se valent.
Le DFS n'a pas cette propriété : il peut atteindre un sommet voisin par un long détour, parce qu'il plonge avant d'explorer les alternatives.
Quiz · 1 question
Un étudiant écrit un parcours en profondeur sans marquer les sommets visités. Que se passe-t-il, et pourquoi la question ne se posait-elle pas au chapitre 7 ?
- Certains sommets sont visités plusieurs fois, ce qui ralentit le parcours sans le fausser — simple ralentissement
- Le parcours boucle indéfiniment dès qu'il existe un cycle, car rien ne l'empêche d'y retourner ; dans un arbre le problème n'existe pas puisqu'il n'y a qu'un chemin depuis la racine et aucun cycle — boucle infinie
- Le parcours s'arrête trop tôt, en manquant les sommets de degré élevé — arrêt prématuré
Réponse : Un arbre est acyclique et chaque nœud n'a qu'un parent : une descente ne peut pas revenir en arrière, le marquage est donc inutile. Un graphe peut contenir un cycle, et rien n'empêche alors le parcours d'y tourner : A visite B, qui visite C, qui revisite A, et ainsi de suite jusqu'au débordement de pile — le même symptôme qu'un cas de base manquant au chapitre 1, pour une cause différente. Même sans cycle, un graphe orienté acyclique où plusieurs chemins mènent au même sommet ferait exploser le nombre de visites de façon exponentielle. Le marquage n'est donc pas une optimisation, c'est ce qui rend le parcours correct — et pour le BFS, il faut marquer à l'ENFILEMENT, pas au défilement, sans quoi un sommet accessible par deux chemins serait enfilé deux fois.
Dijkstra, en introduction
Le BFS répond aux arêtes de poids égal. Dès qu'une route est deux fois plus longue qu'une autre, il ne convient plus : le chemin ayant le moins d'arêtes n'est pas forcément le plus court en distance.
L'algorithme de Dijkstra (1959) traite le cas pondéré, à une condition : tous les poids doivent être positifs. Son principe est glouton, au sens du chapitre suivant — il fait à chaque étape le choix qui paraît le meilleur sur le moment, sans jamais revenir dessus.
distance[départ] ← 0, toutes les autres ← infinitant qu'il reste des sommets non traités u ← le sommet non traité de plus petite distance ← le choix glouton marquer u comme traité pour chaque voisin v de u si distance[u] + poids(u,v) < distance[v] alors distance[v] ← distance[u] + poids(u,v) ← relâchementDeux remarques suffisent à ce niveau.
Le sommet extrait est définitif. Quand on choisit le sommet non traité le plus proche, aucun chemin passant par les sommets restants ne pourra faire mieux — puisqu'ils sont tous plus loin et que les poids sont positifs, tout détour ne peut qu'allonger. C'est ce qui justifie de ne jamais revenir en arrière, et c'est aussi ce qui s'effondre avec un poids négatif : un arc de poids rencontré plus tard pourrait raccourcir un chemin déjà figé.
Le coût dépend de la structure choisie. Chercher le minimum en parcourant tous les sommets donne . Le prendre dans une file de priorité — le tas du chapitre 8 — donne , bien meilleur sur un graphe creux. C'est le plus bel emploi du tas du semestre : Dijkstra a besoin, à chaque étape, du minimum d'un ensemble qui change, ce qui est exactement le contrat de cette structure.
Quiz · 1 question
Pourquoi le parcours en largeur donne-t-il le plus court chemin en nombre d'arêtes, et pourquoi ne suffit-il plus sur un graphe pondéré ?
- Parce qu'il essaie tous les chemins et garde le meilleur ; sur un graphe pondéré il faudrait comparer les sommes, ce qu'il ne fait pas — essai exhaustif
- Parce qu'il explore par couches de distance croissante : quand il atteint un sommet pour la première fois, c'est forcément par le chemin le plus court. Avec des poids, le chemin ayant le moins d'arêtes n'est plus le plus court en distance — exploration par couches
- Parce qu'il utilise une file, structure qui trie automatiquement les chemins par longueur — tri par la file
Réponse : Le BFS n'essaie pas tous les chemins — il visite chaque sommet une seule fois, en O(V+E). Sa propriété vient de l'ORDRE : il traite tous les sommets à distance 1, puis tous ceux à distance 2, etc. La première fois qu'il atteint un sommet, aucune couche antérieure n'y menait, donc le chemin trouvé est minimal en nombre d'arêtes ; mémoriser le prédécesseur suffit à le reconstituer. La file ne trie rien : elle garantit simplement l'ordre d'arrivée, ce qui suffit à préserver l'ordre des couches. Avec des poids, cette équivalence tombe : deux arêtes de poids 1 valent mieux qu'une seule de poids 10, alors que le BFS préférerait la seconde. Il faut alors extraire non plus le plus anciennement enfilé mais le plus proche — d'où le remplacement de la file par une file de PRIORITÉ, et c'est Dijkstra.
À vous
L'exercice construit un petit graphe en listes d'adjacence, puis enchaîne les applications : DFS et BFS, comptage des composantes connexes, détection de cycle, et plus court chemin en nombre d'arêtes avec reconstitution de l'itinéraire — c'est le tableau des prédécesseurs qui fait le travail, et c'est la partie qu'on oublie le plus souvent.
Le squelette contient un DFS sans marquage : lancez-le d'abord sur le graphe cyclique fourni, avec la garde qui l'empêche de tourner à l'infini, et regardez combien de fois chaque sommet est visité. C'est plus convaincant que la mise en garde du cours.
Une dernière partie, facultative, implémente Dijkstra avec une recherche linéaire du minimum, puis vous invite à le rebrancher sur le tas du chapitre 8.
Exercice de code
Écrivez DFS et BFS avec marquage, comptez les composantes, détectez un cycle, puis lancez Dijkstra.
Point de départ
// Listes d'adjacence. Deux composantes connexes, et un cycle dans la première.
const G = {
A: ["B", "C"],
B: ["A", "D"],
C: ["A", "D"],
D: ["B", "C"], // A-B-D-C-A : un cycle
E: ["F"],
F: ["E"], // seconde composante
};
// ── Le parcours SANS marquage, pour voir ──────────────────────────────────
function dfsSansMarquage(g, s, visites = {}, garde = { n: 0 }) {
if (garde.n++ > 60) return visites; // sans cette garde : pile pleine
visites[s] = (visites[s] ?? 0) + 1;
for (const v of g[s]) dfsSansMarquage(g, v, visites, garde);
return visites;
}
// ── Parcours en profondeur ────────────────────────────────────────────────
function dfs(g, depart, vus = new Set(), ordre = []) {
// ← à écrire : marquer, traiter, puis descendre chez les voisins non vus
return ordre;
}
// ── Parcours en largeur, avec prédécesseurs ───────────────────────────────
function bfs(g, depart) {
const vus = new Set([depart]);
const pere = { [depart]: null };
const file = [depart];
const ordre = [];
while (file.length > 0) {
const u = file.shift();
ordre.push(u);
for (const v of g[u]) {
// ← à écrire : marquer À L'ENFILEMENT, noter le père, enfiler
}
}
return { ordre, pere };
}
// Reconstitue le chemin en remontant les pères depuis l'arrivée.
function chemin(pere, arrivee) {
if (!(arrivee in pere)) return null;
const c = [];
for (let s = arrivee; s !== null; s = pere[s]) c.unshift(s);
return c;
}
// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez dfs() et complétez bfs().
// 2. Comptez les composantes connexes de G.
// 3. Détectez le cycle : un voisin déjà vu qui n'est PAS le père immédiat.
console.log("sans marquage :", JSON.stringify(dfsSansMarquage(G, "A")));
Solution
const G = {
A: ["B", "C"], B: ["A", "D"], C: ["A", "D"], D: ["B", "C"],
E: ["F"], F: ["E"],
};
// Un graphe pondéré pour Dijkstra.
const P = {
A: [["B", 4], ["C", 1]],
B: [["A", 4], ["D", 1]],
C: [["A", 1], ["B", 2], ["D", 6]],
D: [["B", 1], ["C", 6]],
};
function dfsSansMarquage(g, s, visites = {}, garde = { n: 0 }) {
if (garde.n++ > 60) return visites;
visites[s] = (visites[s] ?? 0) + 1;
for (const v of g[s]) dfsSansMarquage(g, v, visites, garde);
return visites;
}
function dfs(g, depart, vus = new Set(), ordre = []) {
vus.add(depart); // marquer AVANT de descendre
ordre.push(depart);
for (const v of g[depart]) if (!vus.has(v)) dfs(g, v, vus, ordre);
return ordre;
}
function bfs(g, depart) {
const vus = new Set([depart]);
const pere = { [depart]: null };
const file = [depart];
const ordre = [];
while (file.length > 0) {
const u = file.shift();
ordre.push(u);
for (const v of g[u]) {
if (vus.has(v)) continue;
// Marquer À L'ENFILEMENT : sinon un sommet accessible par deux chemins
// serait enfilé deux fois avant d'être défilé une première fois.
vus.add(v);
pere[v] = u;
file.push(v);
}
}
return { ordre, pere };
}
function chemin(pere, arrivee) {
if (!(arrivee in pere)) return null;
const c = [];
for (let s = arrivee; s !== null; s = pere[s]) c.unshift(s);
return c;
}
function composantes(g) {
const vus = new Set();
const morceaux = [];
for (const s of Object.keys(g)) {
if (vus.has(s)) continue;
morceaux.push(dfs(g, s, vus, [])); // une relance = une composante
}
return morceaux;
}
function aUnCycle(g) {
const vus = new Set();
function explorer(s, pere) {
vus.add(s);
for (const v of g[s]) {
// La nuance qui compte : en non orienté, l'arête par laquelle on est
// arrivé mène évidemment à un sommet déjà vu. Il faut l'exclure.
if (v === pere) continue;
if (vus.has(v)) return true;
if (explorer(v, s)) return true;
}
return false;
}
for (const s of Object.keys(g)) if (!vus.has(s) && explorer(s, null)) return true;
return false;
}
function dijkstra(g, depart) {
const distance = {}, pere = {}, traites = new Set();
for (const s of Object.keys(g)) distance[s] = Infinity;
distance[depart] = 0;
pere[depart] = null;
while (traites.size < Object.keys(g).length) {
// Le choix glouton : le non traité le plus proche. Une file de priorité
// (le tas du chapitre 8) remplacerait cette recherche linéaire.
let u = null;
for (const s of Object.keys(g)) {
if (!traites.has(s) && (u === null || distance[s] < distance[u])) u = s;
}
if (u === null || distance[u] === Infinity) break;
traites.add(u);
for (const [v, poids] of g[u]) {
if (distance[u] + poids < distance[v]) {
distance[v] = distance[u] + poids;
pere[v] = u;
}
}
}
return { distance, pere };
}
console.log("— sans marquage, sur un graphe cyclique —");
console.log(" visites par sommet :", JSON.stringify(dfsSansMarquage(G, "A")));
console.log(" (la garde a coupé à 60 appels ; sans elle, la pile déborde)");
console.log("");
console.log("— avec marquage —");
console.log(" profondeur depuis A :", dfs(G, "A").join(" "));
const b = bfs(G, "A");
console.log(" largeur depuis A :", b.ordre.join(" "));
console.log("");
console.log("composantes connexes :", composantes(G).map((c) => c.join("")).join(" | "));
console.log("contient un cycle :", aUnCycle(G));
console.log("chemin le plus court A -> D :", chemin(b.pere, "D").join(" -> "),
" (" + (chemin(b.pere, "D").length - 1) + " arêtes)");
console.log("");
console.log("— Dijkstra sur le graphe pondéré —");
const d = dijkstra(P, "A");
for (const s of Object.keys(P)) {
console.log(" A -> " + s + " : distance " + String(d.distance[s]).padStart(2) +
" par " + chemin(d.pere, s).join(" -> "));
}
// A -> B coûte 3 en passant par C (1 + 2), pas 4 en direct : c'est
// exactement ce que le BFS ne saurait pas voir, puisqu'il compterait
// une arête contre deux et choisirait la mauvaise.
En travaux pratiques
Travaux pratiques 9 · 4 h
Le calculateur d'itinéraires
Faire converger toute la bibliothèque du semestre sur un problème réel : charger un réseau de transport, le parcourir, et calculer le plus court chemin avec la file de priorité du TP 8.
Avant de commencer
- Les TP 5 à 8 : liste, file, tas, file de priorité
- Un fichier de réseau : arrêts et liaisons avec durées — le vôtre, ou celui d'une ville ouverte
Énoncé
- Choisir la représentation — Représentez le graphe de deux façons : matrice d'adjacence et listes d'adjacence. Mesurez la mémoire de chacune sur votre réseau, et calculez sa densité. Indice : Comptez le rapport entre le nombre d'arêtes et le carré du nombre de sommets.
- Charger le réseau — Lisez le fichier et construisez le graphe. Comptez sommets, arêtes, et vérifiez qu'aucun arrêt cité dans une liaison n'est absent de la liste des arrêts.
- Parcours en largeur — Écrivez le parcours en largeur avec votre file. Utilisez-le pour trouver l'itinéraire en un minimum de CORRESPONDANCES entre deux arrêts, et reconstituez le chemin.
- Parcours en profondeur — Écrivez-le avec votre pile, puis en récursif. Utilisez-le pour compter les composantes connexes du réseau, et identifiez les arrêts isolés.
- Détecter un cycle — Sur un graphe orienté de dépendances — par exemple l'ordre des travaux d'un chantier —, détectez un cycle, puis produisez un ordre topologique quand il n'y en a pas.
- Dijkstra — Implémentez le plus court chemin en TEMPS, avec la file de priorité du TP 8. Comparez le résultat à celui du parcours en largeur et expliquez la différence.
- Mesurer ce que le tas apporte — Écrivez aussi la version de Dijkstra qui cherche le minimum par balayage linéaire. Comparez les deux sur un réseau de mille, puis de cent mille sommets.
- Le piège — Ajoutez au réseau une liaison de durée négative — une correspondance qui ferait gagner du temps. Exécutez Dijkstra et expliquez pourquoi le résultat est faux.
C'est réussi quand
- Votre chargeur signale un arrêt manquant plutôt que de planter
- Le parcours en largeur et Dijkstra donnent des chemins DIFFÉRENTS, et vous savez expliquer lequel répond à quelle question
- La version à tas bat nettement la version linéaire à cent mille sommets
- Vous savez dire précisément quelle hypothèse de Dijkstra une arête négative viole
Correction
réseau : 4 200 arrêts, 9 800 liaisons densité = 9 800 / 4 200² = 0,00055 → graphe CREUX matrice d'adjacence : 4200² × 4 o = 70 Mo (99,9 % de zéros) listes d'adjacence : (4200 + 2×9800) × 16 o = 380 Ko matrice : test d'arête en O(1), parcours des voisins en O(n) listes : test en O(degré), parcours des voisins en O(degré)
Un facteur 180 en mémoire. La règle est la densité : matrice pour un graphe dense ou quand on teste souvent l'existence d'une arête, listes pour un graphe creux — et les graphes réels — routes, réseaux sociaux, dépendances — sont presque toujours creux. Le choix de représentation précède le choix d'algorithme, et le contraint.
void largeur(Graphe *g, int depart, int *distance, int *precedent) {
for (int i = 0; i < g->n; i++) { distance[i] = -1; precedent[i] = -1; }
File f; file_init(&f);
distance[depart] = 0;
enfiler(&f, depart);
while (!file_vide(&f)) {
int u = defiler(&f);
for (Arete *a = g->voisins[u]; a; a = a->suivant)
if (distance[a->vers] == -1) { /* pas encore vu */
distance[a->vers] = distance[u] + 1;
precedent[a->vers] = u; /* pour reconstituer */
enfiler(&f, a->vers);
}
}
}
/* le chemin se relit à l'ENVERS depuis l'arrivée, via precedent */Le tableau precedent est ce qui transforme « à quelle distance » en « par où passer ». On le remplit sans coût supplémentaire, et on relit le chemin à rebours puis on l'inverse — la fonction d'inversion du TP 5 resservant ici. Marquer le sommet au moment de l'ENFILEMENT, et non du défilement, évite de l'enfiler plusieurs fois.
void dijkstra(Graphe *g, int depart, int *dist, int *prec) {
for (int i = 0; i < g->n; i++) dist[i] = INT_MAX;
dist[depart] = 0;
FilePrio f; fp_init(&f);
fp_inserer(&f, depart, 0);
while (!fp_vide(&f)) {
Element e = fp_extraire_min(&f);
if (e.priorite > dist[e.sommet]) continue; /* entrée périmée */
for (Arete *a = g->voisins[e.sommet]; a; a = a->suivant) {
int nouveau = dist[e.sommet] + a->duree;
if (nouveau < dist[a->vers]) {
dist[a->vers] = nouveau;
prec[a->vers] = e.sommet;
fp_inserer(&f, a->vers, nouveau);
}
}
}
}Le test « entrée périmée » remplace la diminution de clé, que le tas simple ne sait pas faire : on réinsère et on ignore les vieilles entrées à l'extraction. C'est la mise en œuvre standard, et elle est correcte parce qu'un sommet est traité la première fois qu'il sort, avec sa plus petite distance. Le parcours en largeur est exactement Dijkstra avec toutes les arêtes de poids 1 — d'où deux chemins différents : le moins de correspondances n'est pas le plus rapide.
1 000 sommets 100 000 sommets minimum par balayage 0,004 s 38 s file de priorité 0,001 s 0,42 s O(n²) contre O((n + m) log n)
Quatre-vingt-dix fois plus rapide, et l'écart croît avec la taille. C'est le retour sur investissement du TP 8 : la structure de données n'accélère pas l'algorithme d'un facteur constant, elle change sa CLASSE de complexité. Sur un graphe dense, en revanche, le balayage linéaire redevient compétitif — la densité décide encore.
A --(5)--> B --(-4)--> C A --(2)--> C Dijkstra traite C en premier (distance 2), le déclare DÉFINITIF, et ne le reconsidère jamais. La vraie distance passe par B : 5 - 4 = 1. → résultat FAUX, sans aucune erreur signalée
Dijkstra repose sur une hypothèse précise : allonger un chemin ne peut pas le raccourcir, donc le sommet le plus proche non traité a sa distance définitive. Un poids négatif détruit cette hypothèse, et l'algorithme se trompe SILENCIEUSEMENT — le pire des comportements. Avec des poids négatifs, il faut Bellman-Ford, plus lent en O(n×m), qui détecte en prime les cycles absorbants.
/* ordre topologique par degrés entrants, avec une file */
compter les degrés entrants
enfiler tous les sommets de degré entrant nul
tant que la file n'est pas vide :
défiler u, l'ajouter au résultat
pour chaque voisin v : décrémenter son degré entrant,
l'enfiler s'il tombe à zéro
si le résultat contient moins de n sommets → il y a un CYCLELe même parcours en largeur, appliqué à un problème qui n'a rien d'un itinéraire : ordonner des tâches dont certaines dépendent d'autres. C'est ce que font make, un gestionnaire de paquets, ou un ordonnanceur de pipeline — et la détection de cycle en est le sous-produit gratuit. Reconnaître qu'un problème est un graphe est plus utile que connaître dix algorithmes de graphes.
Ce que la suite en fait
Le chapitre 10 clôt le semestre en prenant de la hauteur sur les manières de chercher, et Dijkstra y servira d'exemple : c'est un algorithme glouton, dont la correction n'est garantie que sous une hypothèse précise — les poids positifs. C'est exactement ce que le chapitre dira des algorithmes gloutons en général : ils sont rapides et souvent faux, et il faut prouver qu'ils ne le sont pas.
Le parcours en profondeur y reviendra aussi, sous un autre nom : le retour sur trace est un DFS dans un arbre de choix qu'on ne construit jamais explicitement.
À retenir
Flashcards · 5 cartes
- Quand choisir une matrice d'adjacence, quand des listes ?
- Matrice : mémoire O(V²) quel que soit le nombre d'arêtes, test d'arête en O(1), mais énumérer les voisins coûte O(V). Listes : mémoire O(V+E), énumérer les voisins coûte leur degré, mais tester une arête précise demande de parcourir une liste. Comme les parcours ÉNUMÈRENT les voisins et testent rarement une arête isolée, et comme les graphes réels sont massivement creux, les listes sont le choix par défaut.
- Quelle est la seule différence de fond entre parcourir un arbre et parcourir un graphe ?
- Le MARQUAGE des sommets visités. Un arbre est acyclique et chaque nœud n'a qu'un parent : on ne peut pas revenir en arrière. Un graphe peut contenir un cycle, et un parcours non marqué y tourne indéfiniment jusqu'au débordement de pile. Le marquage n'est pas une optimisation, c'est ce qui rend le parcours correct — et en largeur, il faut marquer À L'ENFILEMENT, pas au défilement.
- Comment détecte-t-on un cycle, et comment compte-t-on les composantes connexes ?
- COMPOSANTES : un parcours depuis un sommet atteint exactement sa composante ; on relance depuis chaque sommet non marqué et on compte les relances, en O(V+E). CYCLE en non orienté : le parcours rencontre un sommet déjà marqué QUI N'EST PAS SON PÈRE IMMÉDIAT (sans cette nuance, toute arête serait vue comme un cycle). En orienté : il faut un arc vers un sommet ENCORE EN COURS de traitement dans la pile de récursion, pas simplement déjà visité.
- Pourquoi le BFS donne-t-il le plus court chemin en nombre d'arêtes ?
- Parce qu'il explore par COUCHES de distance croissante : tous les sommets à distance 1, puis tous ceux à distance 2, etc. La première fois qu'il atteint un sommet, aucune couche antérieure n'y menait : le chemin est donc minimal en nombre d'arêtes. Mémoriser le prédécesseur de chaque sommet suffit à reconstituer l'itinéraire. Le DFS n'a pas cette propriété : il plonge avant d'explorer les alternatives, et peut atteindre un voisin par un long détour.
- Sur quel principe repose Dijkstra, et quelle est sa condition de validité ?
- Un principe GLOUTON : à chaque étape on extrait le sommet non traité de plus petite distance, et on le déclare définitif, puis on relâche ses arêtes. C'est valide parce qu'avec des poids POSITIFS, aucun chemin passant par les sommets restants — tous plus loin — ne peut faire mieux. Un poids NÉGATIF casse l'argument : un arc rencontré plus tard pourrait raccourcir un chemin déjà figé. Coût : O(V²) avec une recherche linéaire du minimum, O((V+E) log V) avec un tas.