Tri conditionnel - algorithme, tri

Étant donné N relations du type suivant
par exemple N = 4

A> B

A> C

B> C

D> A

Arrangez l'élément de la relation de telle sorte que pour chaque "xy" consécutif dans l'arrangement "x> y"

La sortie de l'exemple ci-dessus est DABC

Donné N <20

Les relations seront données dans un tableau à deux dimensions

Merci pour votre temps.

Réponses:

Si une telle solution existe - votre problème modélisé en graphique est en réalité un DAG.

Le graphique est G=(V,E) où V= { A,B,C,D} et E = { (x,y) | x < y } = { (B,A),(C,A),(C,B),(A,D) } . [Vous pouvez bien sûr l’étendre pour un plus grand ensemble de sommets, en fonction de l’entrée].

Exécuter un type topologiqueet imprimez les sommets dans l’ordre. Le tri topologique IFF échoue - il n’ya pas de solution, car le graphique a des cycles - les entités n’ont donc pas la possibilité de procéder à un ordre [l’inverse est la même chose].