Tri topologique : ordonner des dépendances

Ordonner des tâches pour que chaque dépendance passe avant ce qui en dépend : c'est un graphe orienté acyclique.

Exemples : ordre de compilation, cours avec prérequis, étapes d'un pipeline CI. L'algorithme de Kahn répète : prendre un sommet sans prérequis restant, l'ajouter au résultat, puis retirer ses arêtes sortantes. Si le résultat ne contient pas tous les sommets, il y a un cycle (ordre impossible). Complexité O(V + E).

Chaque arête [a, b] signifie « a doit passer avant b ».

function topoSort(n: number, edges: [number, number][]): number[] {
  const next: number[][] = Array.from({ length: n }, () => []);
  const indegree = new Array<number>(n).fill(0);
  for (const [a, b] of edges) {
    next[a].push(b);
    indegree[b]++;
  }
  const queue: number[] = [];
  for (let i = 0; i < n; i++) if (indegree[i] === 0) queue.push(i);

  const order: number[] = [];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    order.push(u);
    for (const v of next[u]) if (--indegree[v] === 0) queue.push(v);
  }
  return order.length === n ? order : [];           // [] : cycle détecté
}

Cas pratique : « peut-on suivre tous les cours ? » revient à « ce graphe de prérequis a-t-il un cycle ? ». Un tri topologique qui n'ordonne pas tous les sommets répond non.