Placé
Pas encore placé
Arêtes examinées

  • Actuel
  • Libre ou en cours de visite
  • Placé
  • Cycle

En savoir plus sur le tri topologique

Tri topologique

Les chaussettes avant les chaussures, les fondations avant les murs, un cours avant le cours qui en a besoin. Un tri topologique range les nœuds d'un graphe à arêtes à sens unique sur une ligne où chaque arête pointe vers l'avant. Choisissez l'algorithme de Kahn ou la méthode DFS, avancez pas à pas pour voir l'ordre grandir, et ajoutez un cycle pour voir pourquoi aucun ordre n'est alors possible. Appuyez sur Lecture pour voir l'ordre grandir, ou sur Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où. Chaque arête est à sens unique, comme le montre sa flèche : lisez-la comme « ceci vient avant cela ». Choisissez la méthode : l'algorithme de Kahn place d'abord les nœuds sans arête entrante, et le nombre sur chaque nœud indique combien d'arêtes entrantes il lui reste ; la méthode DFS place chaque nœud devant dès que tout ce qui vient après lui est placé. La ligne sous le graphe est l'ordre obtenu jusqu'ici. Cochez Ajouter un cycle pour voir comment chaque méthode en trouve un. Nouveau graphe crée un autre graphe ; choisissez son nombre de nœuds et d'arêtes. Quand le plateau est sélectionné, les flèches avancent ou reculent d'une étape, la barre d'espace lance et met en pause, et Origine et Fin vont au début et à la fin.

Comment ça marche

  1. Choisissez l'algorithme de Kahn ou la méthode DFS.
  2. Appuyez sur Lecture, ou utilisez Étape et Retour pour avancer pas à pas. Faites glisser le curseur d'étapes pour aller n'importe où.
  3. Regardez l'ordre grandir sous le graphe. Cochez Ajouter un cycle pour voir comment chaque méthode en trouve un.

Algorithme de Kahn

Comptez, pour chaque nœud, combien d'arêtes pointent vers lui. Un nœud qui n'en a aucune ne dépend de rien, il peut donc passer en premier. Placez un tel nœud et retirez ses arêtes sortantes : les nœuds vers lesquels elles pointaient ont une arête entrante de moins, et certains peuvent tomber à zéro et devenir libres. Continuez à placer des nœuds libres jusqu'à ce qu'il n'en reste plus. Si certains nœuds n'ont jamais été libérés, ils s'attendent les uns les autres dans un cycle, et aucun ordre topologique n'existe.

La méthode DFS

Lancez un parcours en profondeur depuis chaque nœud non visité. Un nœud est terminé quand tout ce qui est accessible depuis lui est terminé, donc tout ce qui doit venir après lui est déjà placé. Mettez chaque nœud terminé en tête de l'ordre, et l'ordre est juste. Si le parcours suit une arête vers un nœud dans lequel il se trouve encore, cette arête ferme un cycle, et là encore aucun ordre n'existe.

Questions fréquemment posées

Qu'est-ce qu'un tri topologique ?

Un rangement des nœuds d'un graphe orienté dans lequel chaque arête va d'un nœud placé plus tôt vers un nœud placé plus tard. Si les arêtes signifient « doit venir avant », c'est un ordre dans lequel toutes les tâches peuvent être faites.

Quand un ordre topologique existe-t-il ?

Exactement quand le graphe n'a pas de cycle orienté : c'est un graphe orienté acyclique, ou DAG. Avec un cycle, chaque nœud du cycle devrait venir avant lui-même.

L'ordre topologique est-il unique ?

En général non. Quand deux nœuds ne sont reliés par aucune chaîne d'arêtes, l'un ou l'autre peut passer en premier, donc un graphe peut avoir de nombreux ordres valides. L'algorithme de Kahn et la méthode DFS en donnent souvent des différents.

Un tri topologique est-il rapide ?

Les deux méthodes examinent chaque nœud et chaque arête un nombre fixe de fois, donc le travail croît avec le nombre de nœuds plus le nombre d'arêtes.

Mon graphe est-il envoyé quelque part ?

Non. Le graphe est créé et trié dans votre navigateur, et vos derniers réglages restent dans le stockage local de ce navigateur.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur