Tri Topologique
Dernière mise à jour
Un tri topologique d'un graphe orienté acyclique (DAG) est un ordre linéaire de ses nœuds tel que pour chaque arête u → v, u vient avant v. Il répond à des questions comme « dans quel ordre puis-je exécuter ces tâches pour que chaque prérequis se termine d'abord ? ». Appuyez sur lecture ci-dessus pour voir l'algorithme de Kahn retirer les nœuds dans un ordre valide.
L'algorithme de Kahn prend à plusieurs reprises un nœud sans arêtes entrantes restantes (degré entrant 0), l'ajoute à l'ordre et retire ses arêtes sortantes, ce qui peut libérer de nouveaux nœuds de degré entrant 0. Il ne fonctionne que sur un DAG : s'il existe un cycle, certains nœuds n'atteignent jamais le degré entrant 0 et aucun ordre valide n'existe. Il s'exécute en temps O(V + E).
Complexité en temps et en espace
| Mesure | Complexité | Notes |
|---|---|---|
| Temps | O(V + E) | Chaque nœud émis une fois, chaque arête retirée une fois |
| Espace | O(V) | Compteurs de degré entrant + ensemble prêt + ordre |
| Requiert | Un DAG | Les cycles n'ont pas de tri topologique |
| Résultat | Non unique | De nombreux ordres valides peuvent exister |
Étape par étape (algorithme de Kahn)
| Étape | Ce qui se passe |
|---|---|
| 1 | Calculer le degré entrant (nombre d'arêtes entrantes) de chaque nœud. |
| 2 | Rassembler tous les nœuds de degré entrant 0 dans un ensemble prêt. |
| 3 | Prendre un nœud prêt et l'ajouter à l'ordre de sortie. |
| 4 | Décrémenter le degré entrant de chacun de ses successeurs. |
| 5 | Tout successeur qui atteint le degré entrant 0 rejoint l'ensemble prêt. |
| 6 | Répéter jusqu'à ce que l'ensemble prêt soit vide. |
Exemple résolu
Tri du DAG avec les arêtes A→C, B→C, C→D, C→E, D→F, E→F (degrés entrants initiaux A:0 B:0 C:2 D:1 E:1 F:2) :
| Étape | Ensemble prêt | Ordre | Action |
|---|---|---|---|
| 0 | {A, B} | [] | A et B commencent avec un degré entrant 0, donc les deux sont prêts. |
| 1 | {B} | [A] | Émettre A ; son arête A→C fait passer le degré entrant de C de 2 → 1. |
| 2 | {C} | [A, B] | Émettre B ; son arête B→C fait passer C de 1 → 0, donc C devient prêt. |
| 3 | {D, E} | [A, B, C] | Émettre C ; les arêtes C→D et C→E font passer D et E à 0, tous deux deviennent prêts. |
| 4 | {E} | [A, B, C, D] | Émettre D ; son arête D→F fait passer le degré entrant de F de 2 → 1. |
| 5 | {F} | [A, B, C, D, E] | Émettre E ; son arête E→F fait passer F de 1 → 0, donc F devient prêt. |
| 6 | {} | [A, B, C, D, E, F] | Émettre F ; l'ensemble prêt est vide et les 6 nœuds sont ordonnés : terminé. |
Quand utiliser le tri topologique
| Utilisez-le quand | Évitez-le quand |
|---|---|
| Vous avez besoin d'un ordre qui respecte les dépendances (étapes de compilation, installation de paquets, prérequis de cours). | Le graphe n'est pas orienté : l'ordre topologique n'est défini que pour les graphes orientés. |
| Le graphe est un DAG et vous voulez n'importe quel ordre linéaire valide. | Le graphe peut contenir des cycles et vous avez tout de même besoin d'un ordre total (il n'en existe aucun). |
| Vous voulez détecter les cycles à moindre coût : un tri topologique qui échoue prouve qu'il en existe un. | Vous avez besoin de l'ordre le plus court ou optimal selon un poids ; le tri topologique simple ignore les poids. |
Vous traiterez l'ordre une seule fois en O(V + E). | Les arêtes changent constamment et vous devez re-trier à chaque mise à jour, où une structure incrémentale convient mieux. |
Code de Topological Sort
Une implémentation propre et exécutable de Topological Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Topological Sort en Python
Python
1from collections import deque2
3
4def topological_sort(graph):5 # Kahn's algorithm: repeatedly remove nodes with no incoming edges6 in_degree = {node: 0 for node in graph}7 for node in graph:8 for neighbor in graph[node]:9 in_degree[neighbor] += 110 queue = deque(node for node in graph if in_degree[node] == 0)11 order = []12 while queue:13 node = queue.popleft()14 order.append(node)15 for neighbor in graph[node]:16 in_degree[neighbor] -= 117 if in_degree[neighbor] == 0:18 queue.append(neighbor)19 if len(order) != len(graph):20 raise ValueError("Graph has a cycle, no topological order")21 return order22
23
24graph = {25 "shirt": ["tie", "jacket"],26 "tie": ["jacket"],27 "pants": ["shoes", "jacket"],28 "socks": ["shoes"],29 "shoes": [],30 "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))Code de Topological Sort en JavaScript
JavaScript
1const graph = {2 A: ["C"],3 B: ["C", "D"],4 C: ["E"],5 D: ["F"],6 E: ["F"],7 F: [],8};9
10// Kahn algorithm: repeatedly take a node with no incoming edges11function topologicalSort() {12 const inDegree = {};13 for (const node in graph) inDegree[node] = 0;14 for (const node in graph) {15 for (const next of graph[node]) inDegree[next]++;16 }17 const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);18 const order = [];19 while (queue.length > 0) {20 const node = queue.shift();21 order.push(node);22 for (const next of graph[node]) {23 if (--inDegree[next] === 0) queue.push(next);24 }25 }26 if (order.length !== Object.keys(graph).length) {27 throw new Error("Graph has a cycle");28 }29 return order;30}31
32console.log("Topological order:", topologicalSort().join(" -> "));Code de Topological Sort en Java
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 // DAG: an edge u -> v means u must come before v9 List<List<Integer>> adj = List.of(10 List.of(2),11 List.of(2, 3),12 List.of(4),13 List.of(4),14 List.of(5),15 List.of()16 );17 int[] inDegree = new int[n];18 for (List<Integer> next : adj) {19 for (int v : next) inDegree[v]++;20 }21
22 // Kahn: start from every node with no prerequisites23 Queue<Integer> queue = new ArrayDeque<>();24 for (int i = 0; i < n; i++) {25 if (inDegree[i] == 0) queue.add(i);26 }27
28 StringBuilder order = new StringBuilder("Topological order:");29 while (!queue.isEmpty()) {30 int node = queue.poll();31 order.append(" ").append(node);32 for (int next : adj.get(node)) {33 if (--inDegree[next] == 0) queue.add(next);34 }35 }36 System.out.println(order);37 }38}Code de Topological Sort en C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Directed acyclic graph: adj[u] lists nodes that depend on u7 std::vector<std::vector<int>> adj = {8 {}, // 09 {}, // 110 {3}, // 2 -> 311 {1}, // 3 -> 112 {0, 1}, // 4 -> 0, 113 {0, 2}, // 5 -> 0, 214 };15 int n = static_cast<int>(adj.size());16 std::vector<int> inDegree(n, 0);17 for (const auto& neighbors : adj) {18 for (int v : neighbors) ++inDegree[v];19 }20 // Kahn's algorithm: start from nodes with no incoming edges21 std::queue<int> ready;22 for (int u = 0; u < n; ++u) {23 if (inDegree[u] == 0) ready.push(u);24 }25 std::cout << "Topological order: ";26 while (!ready.empty()) {27 int u = ready.front();28 ready.pop();29 std::cout << u << " ";30 // Removing u unlocks neighbors whose in-degree drops to 031 for (int v : adj[u]) {32 if (--inDegree[v] == 0) ready.push(v);33 }34 }35 std::cout << "\n";36 return 0;37}Code de Topological Sort en C
C
1#include <stdio.h>2
3#define N 64
5int main(void) {6 // Directed acyclic graph: adj[u][v] = 1 means an edge u -> v7 int adj[N][N] = {0};8 adj[2][3] = 1;9 adj[3][1] = 1;10 adj[4][0] = 1;11 adj[4][1] = 1;12 adj[5][0] = 1;13 adj[5][2] = 1;14 int inDegree[N] = {0};15 for (int u = 0; u < N; u++) {16 for (int v = 0; v < N; v++) inDegree[v] += adj[u][v];17 }18 // Kahn's algorithm: start from nodes with no incoming edges19 int queue[N];20 int head = 0, tail = 0;21 for (int u = 0; u < N; u++) {22 if (inDegree[u] == 0) queue[tail++] = u;23 }24 printf("Topological order: ");25 while (head < tail) {26 int u = queue[head++];27 printf("%d ", u);28 // Removing u unlocks neighbors whose in-degree drops to 029 for (int v = 0; v < N; v++) {30 if (adj[u][v] && --inDegree[v] == 0) queue[tail++] = v;31 }32 }33 printf("\n");34 return 0;35}FAQ sur le tri topologique
À quoi sert un tri topologique ?
Il ordonne les tâches pour que chaque dépendance vienne avant ce qui en a besoin. Les usages réels incluent les systèmes de compilation et les gestionnaires de paquets (compiler les dépendances d'abord), la planification de cours avec prérequis et l'ordre d'évaluation des formules dans les tableurs.
Quelle est la complexité en temps du tri topologique ?
L'algorithme de Kahn comme l'approche fondée sur le DFS s'exécutent en temps
O(V + E), car chaque nœud est traité une fois et chaque arête est examinée une fois. Ils utilisent O(V) d'espace supplémentaire.Pourquoi le tri topologique nécessite-t-il un DAG ?
Un cycle orienté crée une contradiction : si
a doit venir avant b et b doit venir avant a, aucun ordre linéaire ne satisfait les deux. Ainsi, un tri topologique existe si et seulement si le graphe est un graphe orienté acyclique. L'algorithme de Kahn détecte un cycle lorsqu'il se termine avant d'avoir émis tous les nœuds.Quelle est la différence entre l'algorithme de Kahn et le tri topologique par DFS ?
L'algorithme de Kahn est itératif et proche du BFS : il retire à plusieurs reprises les nœuds de degré entrant 0, ce qui rend la détection de cycle et l'ordonnancement entièrement explicites. L'approche DFS visite les nœuds récursivement et place chacun en tête de l'ordre lorsque sa récursion se termine, produisant l'inverse des temps de fin. Les deux sont en
O(V + E) ; celui de Kahn évite la récursion profonde et expose naturellement l'ensemble prêt, tandis que le DFS est souvent plus court à écrire.Quand dois-je utiliser un tri topologique plutôt qu'un tri classique ?
Utilisez le tri topologique lorsque l'ordre est défini par des dépendances entre éléments plutôt que par une clé comparable. Un tri par comparaison comme le tri fusion
O(n log n) ordonne par valeur ; le tri topologique ordonne selon des arêtes « doit venir avant » et, contrairement à un tri par comparaison, peut produire de nombreuses réponses valides pour la même entrée.Le résultat d'un tri topologique est-il unique ?
Généralement non. Dès que deux nœuds ou plus sont prêts (degré entrant 0) en même temps, vous pouvez les émettre dans n'importe quel ordre, donc la plupart des DAG admettent plusieurs tris topologiques valides. L'ordre n'est unique que lorsqu'il y a exactement un nœud prêt à chaque étape, ce qui se produit lorsque le DAG forme une seule chaîne (un chemin hamiltonien).
Ressources associées
Plus de visualisations
