Wenn die Zahlen 0,1,2 Knoten in einem gerichteten azyklischen Graphen sind und wir nur 1 Kante haben: 1 -> 2. Dann sind alle gültigen Bestellungen:Topologische Sortierreihenfolgen bei einem getrennten DAG
1,2,0
0,1,2
1,0,2
Bin ich richtig? Ich bin nur nicht sicher über die letzte Bestellung: 1,0,2 Ist es gültig?
Ja, Sie haben Recht.
Nach dem definition, die einzige Bedingung für topologischen Anordnung ist, dass für jede gerichtete Kante u->v u vor v kommen sollte. Es ist nicht gesagt, dass es kurz vor v kommen sollte.
die Eckpunkte Betrachten Aufgaben darstellen ausgeführt werden, sagen Sie, dass Sie sich fertig machen. Say 0 zieht eine Krawatte an, 1 trägt ein Paar Socken und 2 trägt Schuhe. Also kommt 1 vor 2 (1-> 2). Wie Sie sehen können, kann die letzte Bestellung, die Sie geschrieben haben, als eine topologische Bestellung angesehen werden (Tragen Sie Socken, dann binden Sie und dann Ihre Schuhe)