Das Problem des Topologischen Sortierens auf einem gerichteten Graphen
besteht darin, eine Knoten-Nummerierung f : V
zu finden, die mit
den Kantenrichtungen kompatibel ist,
d.h.
.
Begonnen wird die Nummerierung bei einem Knoten mit Eingangsgrad 0 (der die erste Nummer erhalten kann).
Sei der Knoten, der zuletzt nummeriert wurde. Dann werden
nun die von
ausgehenden Kanten (virtuell) entfernt
und somit die (virtuellen) Eingangsgrade der von ihm erreichbaren Knoten
vermindert. Verwendet wird dabei
eine Schlange, welche solche Knoten speichert, deren virtueller Eingangsgrad
im Laufe der Berechnung inzwischen auf 0 gesunken ist und daher
für die nächste zu vergebene Nummer infrage kommt. Auf diese Weise wird
verhindert, dass immer wieder nach einem Knoten mit Eingangsgrad
gesucht werden muss.
Source: TopoSort.java JavaDoc: TopoSort.html