Topologische Sortierung

Sei ein gerichteter Graph, dann heißt eine bijektive Funktion

eine topologische Sortierung von , wenn gilt:

Einfach gesagt

• Eingabe: Gerichteter Graph
• Ausgabe: Totalordnung der Knoten (Zuordnung der Reihenfolgennummer)

Die topologische Sortierung stellt sicher, dass an jeder beliebigen Kante gilt, dass die Nummer des Startknotens kleiner ist als die Nummer des Zielknotens.

Es darf nie ein Kindknoten vor einem Elternknoten kommen.

Eine topologische Sortierung ist nur in gerichteten azyklischen Graphen (engl. directed acyclic graph, DAG) möglich.

Implementierung

Die topologische Sortierung kann durch Tiefensuche ermittelt werden. Die Folge der “fertig verarbeiteten Knoten” einer Tiefensuche liefert eine umgekehrte topologische Sortierung.

• Benutze den Algorithmus zur Tiefensuche
• Immer, wenn ein Knoten schwarz wird, wird er vorne an eine lineare, verkettete Liste eingefügt