Algorithme de Kahn : tri topologique par BFS
Calculez les degrés entrants de tous les nœuds, placez dans une file ceux dont le degré entrant est nul et traitez la file pour produire un ordre topologique tout en détectant les cycles.
Algorithme de Kahn : tri topologique par BFS est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’un tri topologique ?
Un tri topologique d’un graphe orienté acyclique (DAG) est un ordre de ses nœuds tel que toute arête orientée u → v signifie que u précède v dans cet ordre. Il représente un ordre d’exécution valide pour des tâches ayant des dépendances, comme dans les systèmes de compilation, la planification de cours ou la gestion de paquets. Seuls les DAG possèdent un ordre topologique valide ; un cycle le rend impossible.
Algorithme de Kahn : idée centrale
L’algorithme de Kahn est une approche fondée sur le BFS pour effectuer un tri topologique. L’idée essentielle est qu’un nœud de degré entrant nul (sans prérequis) peut être placé en premier dans l’ordre. Après l’avoir placé, retirez-le et décrémentez le degré entrant de ses voisins. Les nouveaux nœuds de degré entrant nul deviennent disponibles. Répétez jusqu’à ce que tous les nœuds soient placés ou qu’un cycle soit détecté (des nœuds conservent un degré entrant non nul).
Calcul du degré entrant
Commencez par construire la liste d’adjacence et calculer le degré entrant (le nombre d’arêtes entrantes) de chaque nœud. Les nœuds de degré entrant nul sont les points de départ : ils n’ont aucune dépendance. Pour un graphe dont les arêtes sont [(0,1),(0,2),(1,3),(2,3)], les degrés entrants sont : 0→0, 1→1, 2→1, 3→2. Seul le nœud 0 commence avec un degré entrant nul.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Implémentation de l’algorithme de Kahn
Mettez en file tous les nœuds de degré entrant nul. Traitez chaque nœud : ajoutez-le au résultat, puis, pour chaque voisin, décrémentez son degré entrant et mettez-le en file s’il atteint 0. Si la liste de résultats contient moins de nœuds que le graphe, un cycle existe : certains nœuds n’auraient jamais pu être retirés de la file.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Détection des cycles avec Kahn
L’algorithme de Kahn offre une détection des cycles sans coût supplémentaire : si len(order) < n, certains nœuds n’ont jamais été ajoutés à la file parce que leur degré entrant n’a jamais atteint 0 ; ils font partie d’un cycle. Cette méthode est plus claire que le maintien d’un tableau de nœuds visités avec un code couleur. Renvoyez une liste vide pour signaler l’existence d’un cycle.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Complexité temporelle et spatiale
L’algorithme de Kahn traite chaque nœud une fois (un seul retrait de la file) et chaque arête une fois (un seul décrément du degré entrant). Complexité temporelle : O(V + E). Espace : O(V + E) pour la liste d’adjacence et le tableau des degrés entrants, plus O(V) pour la file. Cette complexité est optimale : vous devez au minimum lire tous les nœuds et toutes les arêtes pour produire un ordre valide.
Ordre topologique lexicographiquement minimal
L’algorithme de Kahn avec un tas-min à la place d’une file produit l’ordre topologique lexicographiquement minimal. Remplacez deque par heapq : insérez (node) et traitez toujours en premier le plus petit nœud disponible. Cela garantit l’ordre valide lexicographiquement minimal parmi tous les tris topologiques possibles.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Application : planification des cours I
Planification des cours (LeetCode 207) : étant donné n cours et leurs prérequis, pouvez-vous terminer tous les cours ? Modélisez les prérequis par des arêtes orientées et vérifiez si un tri topologique valide existe, c’est-à-dire s’il n’y a aucun cycle. Renvoyez vrai si l’algorithme de Kahn produit un ordre de longueur n, et faux si un cycle est détecté.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Application : planification des cours II
Planification des cours II (LeetCode 210) : renvoyez l’ordre réel dans lequel suivre les cours. Le principe est le même que ci-dessus, mais renvoyez la liste order au lieu d’un booléen. Si un cycle existe, renvoyez une liste vide. Cette solution utilise directement le résultat de l’algorithme de Kahn comme réponse.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Planification de tâches en parallèle
Une utilisation plus avancée consiste, étant donné des tâches avec des dépendances, à trouver le nombre minimal de « tours » nécessaires si les tâches sans dépendances peuvent s’exécuter en parallèle. Traitez les niveaux de Kahn comme dans un parcours BFS par niveaux : mettez en file tous les nœuds de degré entrant nul, traitez toute la file actuelle comme un seul tour, puis mettez en file les nœuds nouvellement libérés pour le tour suivant. Comptez les tours.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Tri topologique et DP sur les DAG
Le tri topologique permet d’effectuer une programmation dynamique sur les DAG : traitez les nœuds dans l’ordre topologique et, lors du calcul de dp[v], tous les prédécesseurs dp[u] ont déjà une valeur définitive. Cette technique combine le tri topologique et la DP pour résoudre des problèmes comme le plus long chemin dans un DAG, le coût minimal pour atteindre tous les nœuds ou le profit maximal issu d’une chaîne de dépendances. L’ordre garantit que la valeur de DP de chaque nœud est calculée exactement une fois, après toutes ses dépendances.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Vérification rapide
Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation de cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : l’algorithme de Kahn calcule le tri topologique en retirant itérativement les nœuds de degré entrant nul avec un BFS, la détection des cycles est sans coût supplémentaire : si len(order) < n, un cycle existe, et remplacer la file par un tas-min donne l’ordre topologique lexicographiquement minimal. Ensuite, nous explorerons le tri topologique fondé sur le parcours postfixe de DFS comme solution de remplacement à l’algorithme de Kahn.
Questions Fréquemment Posées
La leçon « Algorithme de Kahn : tri topologique par BFS » est-elle gratuite ?
Oui — le texte complet de « Algorithme de Kahn : tri topologique par BFS » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Algorithme de Kahn : tri topologique par BFS » ?
Calculez les degrés entrants de tous les nœuds, placez dans une file ceux dont le degré entrant est nul et traitez la file pour produire un ordre topologique tout en détectant les cycles. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Algorithme de Kahn : tri topologique par BFS » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Algorithme de Kahn : tri topologique par BFS
- Tri topologique par DFS en post-ordre
- Planification de cours I et II
- Composantes fortement connexes avec Kosaraju