Für die Aufgaben A bis E gelten die Reihenfolgebedingungen „A vor C“, „B vor C“, „C vor D“, „B vor E“ und „E vor D“. Welche Reihenfolge erfüllt alle Bedingungen (ein Ergebnis der topologischen Sortierung)?

Antwort: B. B, A, E, C, D

In B, A, E, C, D stehen A und B vor C, C und E vor D, und B vor E; alle fünf Bedingungen sind also erfüllt. A, C, B, E, D führt C vor B aus und verletzt „B vor C“, und B, E, D, A, C führt D vor C aus und verletzt „C vor D“. Die topologische Sortierung ordnet die Knoten eines gerichteten azyklischen Graphen (DAG) so an, dass jede Kante von einem früheren zu einem späteren Knoten zeigt; sie gelingt, indem man wiederholt einen Knoten ohne eingehende Kanten entnimmt (Kahn-Algorithmus), oder mit einer Tiefensuche. Das Ergebnis ist nicht immer eindeutig: In diesem Beispiel gibt es fünf gültige Reihenfolgen.