Tri topologique avec l’algorithme de Kahn
Ordonner les tâches qui dépendent les unes des autres
Tri topologique avec l’algorithme de Kahn est une leçon Competitive Programming Academy 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 Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Définition d’un ordre topologique
Un ordre topologique répertorie chaque nœud d’un graphe orienté de sorte que chaque arête aille d’un nœud antérieur à un nœud ultérieur. Pensez aux tâches à effectuer avant celles qui en dépendent.
Seuls les DAG sont autorisés
Cela ne fonctionne que sur un DAG, c’est-à-dire un graphe orienté acyclique. S’il existe un cycle, aucun ordre valide ne peut respecter toutes les dépendances.
L’idée du degré entrant
L’algorithme de Kahn repose sur le degré entrant : le nombre d’arêtes qui arrivent sur un nœud. Un nœud de degré entrant nul n’a aucune dépendance non satisfaite.
Compter chaque degré entrant
Première passe : parcourez toutes les arêtes et comptez combien de fois chaque nœud est une destination. Vous obtenez ainsi le degré entrant de chaque nœud.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Initialiser la file des nœuds prêts
Tout nœud de degré entrant nul est immédiatement prêt : ajoutez-les tous à une file pour commencer.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Traiter un nœud
Appliquez pop à un nœud prêt, puis ajoutez-le à votre ordre avec append. Il peut être placé sans risque, car plus rien n’en dépend.
u = q.popleft()
order.append(u)Libérer ses voisins
Pour chaque voisin, réduisez son degré entrant de un. Lorsqu’un voisin atteint zéro, il devient prêt et rejoint la file.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Répéter jusqu’à épuisement
Continuez à appliquer pop et à libérer les voisins jusqu’à ce que la file soit vide. L’ordre s’enrichit d’un nœud sûr à la fois, jusqu’à ce que tous les nœuds soient placés.
Détecter gratuitement un cycle
Si votre ordre final contient moins de n nœuds, un cycle a bloqué les autres. L’algorithme de Kahn fournit donc la détection des cycles sans coût supplémentaire.
if len(order) < n:
print('cycle exists')Le temps d’exécution
Chaque nœud et chaque arête sont parcourus une fois, donc l’algorithme de Kahn s’exécute en O(V + E). Il peut ainsi traiter des graphes comportant des millions d’arêtes.
De nombreux ordres valides
Lorsque plusieurs nœuds sont prêts en même temps, n’importe lequel peut être choisi ensuite. Un DAG possède donc souvent de nombreux ordres topologiques valides, et pas un seul.
Vérification rapide
Vous terminez l’algorithme de Kahn, mais l’ordre contient moins de n nœuds. Qu’est-ce que cela signifie ?
Récapitulatif : l’algorithme de Kahn
Comptez les degrés entrants, mettez les nœuds de degré nul dans la file, appliquez pop à un nœud, décrémentez les degrés de ses voisins, puis recommencez. Vous obtenez ainsi un tri topologique clair en O(V+E). 🚀
Questions Fréquemment Posées
La leçon « Tri topologique avec l’algorithme de Kahn » est-elle gratuite ?
Oui — le texte complet de « Tri topologique avec l’algorithme de Kahn » 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 Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Tri topologique avec l’algorithme de Kahn » ?
Ordonner les tâches qui dépendent les unes des autres Tu pratiques Competitive Programming Academy 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 Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy 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 « Tri topologique avec l’algorithme de Kahn » ?
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 Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy 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
- Tri topologique avec l’algorithme de Kahn
- Détecter les cycles dans les graphes orientés
- Composantes fortement connexes
- Ponts et points d’articulation