Qu'est-ce qu'un tri topologique ?

C'est un ordonnancement des sommets d'un graphe orienté tel que pour chaque arête orientée de u vers v, u apparaît avant v dans l'ordonnancement — possible seulement lorsque le graphe n'a pas de cycles.

Comment fonctionne l'algorithme de Kahn ?

Il trouve de manière répétée un nœud avec zéro arête entrante restante (aucun prérequis non traité), le retire et l'ajoute à l'ordre de sortie, puis diminue le degré entrant de ses voisins, répétant jusqu'à ce que chaque nœud soit traité.

Que se passe-t-il si le graphe a un cycle ?

L'algorithme se bloque — certains nœuds auront toujours au moins une arête entrante depuis l'intérieur du cycle, donc ils ne sont jamais retirables, et la calculatrice signale qu'aucun ordre topologique valide n'existe.

L'ordre topologique est-il toujours unique ?

Non — lorsque plusieurs nœuds ont zéro arête entrante en même temps, n'importe lequel d'entre eux pourrait venir ensuite, donc un graphe peut avoir plusieurs ordres topologiques valides. Cette calculatrice en choisit un de manière cohérente en utilisant un départage alphabétique.

En quoi cela diffère-t-il de l'algorithme de Dijkstra ?

L'algorithme de Dijkstra trouve les chemins les plus courts dans un graphe pondéré ; le tri topologique trouve un ordre de traitement valide dans un graphe orienté basé purement sur la structure de dépendance, sans aucune notion de poids ou de distance d'arête.

Que signifie '->' dans la saisie des arêtes ?

Il indique la direction — A->B signifie qu'il y a une arête orientée de A vers B (A doit venir avant B), contrairement au format non orienté 'A-B' utilisé par les autres outils de graphe du site.

Combien de nœuds cette calculatrice peut-elle gérer ?

Cette calculatrice prend en charge jusqu'à 50 nœuds, gardant l'algorithme de Kahn instantané tout en couvrant la grande majorité des graphes de dépendances saisis à la main.

Où le tri topologique est-il utilisé dans la vie réelle ?

Il est utilisé dans les systèmes de build et les compilateurs (compilation de fichiers dans l'ordre de dépendance), les gestionnaires de paquets (installation des dépendances avant les paquets qui en ont besoin), les planificateurs de tâches, et l'ordre d'évaluation des formules de tableur.

Calculatrice de Tri Topologique — Ordonnez des Tâches selon Leurs Dépendances

Notre Calculatrice de Tri Topologique trouve un ordonnancement valide des nœuds d'un graphe orienté tel que chaque arête pointe d'un nœud antérieur vers un nœud postérieur — exactement l'ordonnancement dont vous avez besoin pour planifier des tâches dépendantes — à l'aide de l'algorithme de Kahn, et signale clairement quand un tel ordonnancement n'existe pas parce que le graphe contient un cycle.

Réponse rapide

Saisissez votre graphe orienté sous forme de liste d'arêtes pour trouver instantanément un ordre topologique valide via l'algorithme de Kahn, ou détecter qu'un cycle rend l'ordonnancement impossible.

Arêtes orientées (séparées par des virgules)

Saisissez des arêtes orientées sous la forme NœudA->NœudB, par ex. A->B, A->C, B->D.

Comment utiliser Calculatrice de Tri Topologique — Algorithme de Kahn en Ligne

1
Saisissez votre graphe orienté sous forme de liste d'arêtes séparées par des virgules, par ex. A->B, A->C, B->D.
2
Cliquez sur 'Calculer' pour trouver un ordre topologique valide.
3
Consultez l'ordre résultant, ou le message de cycle détecté si aucun ordre n'existe.

Pourquoi utiliser Calculatrice de Tri Topologique — Algorithme de Kahn en Ligne ?

Un tri topologique organise les nœuds d'un graphe orienté acyclique en une ligne où chaque arête pointe vers l'avant — exactement la structure nécessaire pour planifier des tâches avec des dépendances, compiler des fichiers dans le bon ordre, ou résoudre l'ordre d'installation de paquets. L'algorithme de Kahn le trouve directement : retirer de manière répétée tout nœud sans arêtes entrantes restantes et l'ajouter à l'ordre, en mettant à jour le graphe restant au fur et à mesure. Si le processus manque de nœuds retirables avant que chaque nœud soit placé, le graphe doit contenir un cycle, ce qui signifie qu'aucun ordonnancement valide n'existe du tout — cette calculatrice détecte ce cas explicitement plutôt que de renvoyer un ordre partiel ou incorrect.

Questions fréquentes

Outils similaires

Calculatrice du Plus Court Chemin de Dijkstra — Graphes Pondérés en Ligne

Trouvez le plus court chemin et la distance totale entre deux nœuds dans un graphe pondéré à l'aide de l'algorithme de Dijkstra. Calculatrice gratuite avec une simple saisie de liste d'arêtes.

Calculatrice de Matrice d'Adjacence — Construisez une Matrice de Graphe en Ligne

Construisez et affichez la matrice d'adjacence d'un graphe à partir d'une simple saisie de liste d'arêtes, avec sa séquence de degrés. Calculatrice gratuite, pondérée ou non pondérée.

Vérificateur de Chemin Hamiltonien — Visitez Chaque Nœud Une Fois en Ligne

Vérifiez si un graphe a un chemin hamiltonien — un chemin visitant chaque nœud exactement une fois — via une recherche par retour sur trace. Calculatrice gratuite, limitée aux graphes de jusqu'à 10 nœuds.