Abhängigkeitsreihenfolge per Graphtraversierung: BFS, DFS und topologische Sortierung

Ziel

Für Elemente, die voneinander abhängen (Build-Ziele, Datenbankmigrationen, Deployment-Schritte, Module), eine Reihenfolge berechnen, in der jedes Element nach allen seinen Abhängigkeiten kommt, Zyklen ausdrücklich melden und die Menge der Elemente finden, die von einer Änderung betroffen sind.

Voraussetzungen

Eine Liste von Knoten und gerichteten Kanten mit einer festen Lesart, zum Beispiel "A muss vor B laufen". Beide Richtungen funktionieren, solange das gesamte Programm eine davon durchgängig verwendet. Knotenidentitäten müssen eindeutig und vergleichbar sein, damit Gleichstände deterministisch aufgelöst werden können.

Schritte

1. Zwei Adjazenzlisten aufbauen (Abhängigkeiten jedes Knotens, Abhängige jedes Knotens) sowie einen Eingangsgrad je Knoten zählen; Knoten ohne jede Kante mit einbeziehen.
2. Betroffene Menge per Traversierung: ausgehend von einem geänderten Knoten den Abhängigen-Kanten folgen und besuchte Knoten sammeln. Breitensuche mit einer Warteschlange besucht nach Distanz, was direkte von transitiven Abhängigen trennt; Tiefensuche mit einem expliziten Stack ist für die Menge gleichwertig. Knoten als besucht markieren, bevor sie eingereiht werden, damit gemeinsame Teilgraphen und Zyklen nicht zu Schleifen führen.
3. Sortierung mit Kahns Algorithmus: jeden Knoten mit Eingangsgrad null einreihen; einen entnehmen, ausgeben, den Eingangsgrad jedes Abhängigen verringern und jene, die null erreichen, einreihen. Nie ausgegebene Knoten liegen auf oder hinter einem Zyklus; sie namentlich melden.
4. Alternative Sortierung mit DFS-Nachordnung: einen Knoten besuchen, in seine Abhängigkeiten rekursiv absteigen, ihn dann anhängen. Ein Knoten, der noch als "in Bearbeitung" angetroffen wird, schliesst einen Zyklus; den Pfad für die Fehlermeldung aufzeichnen. Die Anhängereihenfolge ist eine gültige Abhängigkeitsreihenfolge.
5. Parallele Planung: die in Kahns Algorithmus gleichzeitig bereiten Knoten können parallel laufen. Pythons graphlib.TopologicalSorter stellt das über prepare(), get_ready() und done() bereit, und prepare() wirft CycleError, wenn ein Zyklus besteht. GNU tsort liest Paare und schreibt eine Gesamtordnung, die mit der übergebenen Teilordnung verträglich ist.
6. Gleichstände durch Sortieren der bereiten Menge nach Namen deterministisch machen; sonst kann jeder Lauf eine andere gültige Reihenfolge erzeugen, und Builds werden irreproduzierbar.
7. Mit einem Diamanten (A vor B und C, beide vor D), einem Zyklus, einem isolierten Knoten und einer langen Kette testen, um die Tiefenbehandlung zu prüfen.

Erwartetes Ergebnis

Eine reproduzierbare Reihenfolge, ein Zyklus-Bericht, der die beteiligten Knoten benennt, und eine betroffene Menge, die sich für inkrementelle Builds oder gezielte Testläufe verwenden lässt.

Grenzen und Prüfbasis

Nur azyklische Graphen besitzen eine topologische Ordnung; ein Zyklus ist ein zu behebender Modellierungsfehler, kein Umweg. Nicht deklarierte Abhängigkeiten erzeugen eine Reihenfolge, die gültig aussieht und falsch ist; der Algorithmus kann fehlende Kanten nicht erkennen. Rekursives DFS ist bei langen Ketten tiefenbegrenzt; die iterative Form vorziehen. Das Verhalten der Bibliotheken entspricht der zitierten Dokumentation.