Graphes

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.

Deux notations utiles : $V$ pour le nombre de sommets, $E$ pour le nombre d'arêtes. Un graphe est dit dense quand $E$ approche $V^2$ — presque tout est relié — et creux quand $E$ est de l'ordre de $V$. Cette distinction décide de la représentation.

Deux représentations

La matrice d'adjacence est un tableau $V \times V$ où la case $(i,j)$ vaut 1 s'il existe une arête de $i$ vers $j$ — ou le poids, s'il y en a un.

1        A  B  C  D              A ── B2     A  0  1  1  0              │    │3     B  1  0  1  0              C ───┘4     C  1  1  0  1              │5     D  0  0  1  0              D

Tester l'existence d'une arête est en $O(1)$, ce qui est imbattable. Mais la mémoire est $O(V^2)$ quel que soit le nombre d'arêtes, et surtout, énumérer les voisins d'un sommet demande de parcourir toute une ligne, soit $O(V)$ — même s'il n'a que deux voisins.

Les listes d'adjacence associent à chaque sommet la liste de ses voisins.

1A : B, C2B : A, C3C : A, B, D4D : C

La mémoire est $O(V + E)$, 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.

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 $10^{14}$ 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.

1fonction profondeur(s)2    marquer s3    traiter s4    pour chaque voisin v de s5        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.

1fonction largeur(s)2    marquer s ; enfiler s3    tant que la file n'est pas vide4        u ← défiler5        traiter u6        pour chaque voisin v de u non marqué7            marquer v ; enfiler v

Un 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 $O(V + E)$ 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 $O(V+E)$.

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.

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.

1distance[départ] ← 0, toutes les autres ← infini2tant qu'il reste des sommets non traités3    u ← le sommet non traité de plus petite distance      ← le choix glouton4    marquer u comme traité5    pour chaque voisin v de u6        si distance[u] + poids(u,v) < distance[v] alors7            distance[v] ← distance[u] + poids(u,v)        ← relâchement

Deux 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 $-5$ 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 $O(V^2)$. Le prendre dans une file de priorité — le tas du chapitre 8 — donne $O((V+E)\log V)$, 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.

À 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.

// 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")));

En travaux pratiques

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