Gerichtete Tiefensuche (DFS) und topologische Nummerierung
Die gerichtete Tiefensuche ist ein algorithmisches Basiswerkzeug, das den Graphen entlang der ausgehenden Kanten traversiert und die Knoten über eine Post-Order-Nummerierung klassifiziert.
- Algorithmus: Das System initialisiert ein globales Array
für alle Knoten. Solange unbesuchte Knoten existieren, wird die rekursive Routine gestartet:
Algorithmus rec-DFS(v):
Bestimme M(v) = {w in V(G) | m(w) == \perp und (v, w) in E(G)}
Wenn M(v) nicht leer:
Wähle ein u aus M(v)
c = rec-DFS(u)
Setze m(v) = c
Gib c + 1 zurück
- Post-Order-Eigenschaft: Der Algorithmus weist einem Knoten seine finale Nummerierung
erst dann zu, wenn alle von ihm aus erreichbaren Pfade vollständig exploriert wurden. Gilt für zwei Knoten, dass von aus erreichbar ist, aber nicht von erreicht werden kann, so gilt zwingend die relationale Ordnung: .