Topologisches Sortieren

Das Problem des Topologischen Sortierens auf einem gerichteten Graphen besteht darin, eine Knoten-Nummerierung f : V $\rightarrow \Bbb{N}$ zu finden, die mit den Kantenrichtungen kompatibel ist, d.h. $(x,y) \in E \Rightarrow f(x) < f(y)$.

Begonnen wird die Nummerierung bei einem Knoten mit Eingangsgrad 0 (der die erste Nummer erhalten kann).

Sei $x$ der Knoten, der zuletzt nummeriert wurde. Dann werden nun die von $x$ 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 $0$ gesucht werden muss.

Topologisches Sortieren: Knoten A nummeriert, Nachfolgekanten entfernt

Source: TopoSort.java     JavaDoc: TopoSort.html