Topologische Sortierung per DFS-Postorder
Führen Sie DFS aus und legen Sie jeden Knoten auf einen Stack, nachdem seine Nachbarn vollständig erkundet wurden. Entnehmen Sie anschließend die Knoten vom Stack, um eine gültige topologische Reihenfolge zu erhalten.
Topologische Sortierung per DFS-Postorder ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Idee der topologischen Sortierung auf Basis von DFS
Der zweite klassische Algorithmus zur topologischen Sortierung verwendet DFS mit einer Verarbeitung in Postorder. Nachdem alle Nachbarn eines Knotens (und deren Nachfolger) vollständig untersucht wurden, wird der Knoten auf einen Stack gelegt. Wenn alle Knoten verarbeitet sind, wird der Stack geleert, um die topologische Reihenfolge abzulesen. Ein Knoten, der erst nach all seinen Abhängigkeiten auf den Stack gelegt wird, kommt in der Reihenfolge zuerst — daher ergibt die umgekehrte Postorder die topologische Sortierung.
Intuition hinter der Postorder
Betrachten Sie einen Abhängigkeitsgraphen, in dem Kurs A Kurs B voraussetzt. Wenn DFS A besucht, ruft es zuerst rekursiv B auf. B hat keine Voraussetzungen, wird also zuerst fertig und zuerst auf den Stack gelegt. Danach wird A fertig und ebenfalls auf den Stack gelegt. Beim Leeren des Stacks steht A in der Ausgabe vor B — am Ende kehren wir die Reihenfolge jedoch um, sodass B vor A steht: zuerst B, dann A. Die Postorder legt Abhängigkeiten vor den von ihnen abhängigen Knoten ab, sodass der umgekehrte Stack eine gültige topologische Reihenfolge ergibt.
Dreifarbige DFS zur Zykluserkennung
Verwenden Sie drei Zustände für besuchte Knoten: WHITE (0) = unbesucht, GREY (1) = wird gerade verarbeitet (befindet sich im DFS-Aufruf-Stack), BLACK (2) = vollständig verarbeitet. Eine Rückkante — eine Kante zu einem GREY-Knoten — weist auf einen Zyklus hin. Kanten zu BLACK-Knoten sind unproblematisch (diese wurden bereits vollständig untersucht). Dieses Dreifarbenschema erkennt alle Zyklen in gerichteten Graphen korrekt.
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n # n = number of nodes
# During DFS:
# color[node] = GREY (entering node)
# recurse into neighbours
# if neighbour is GREY: cycle found!
# color[node] = BLACK (leaving node, push to stack)Vollständige Implementierung der topologischen Sortierung mit DFS
Verwenden Sie eine rekursive DFS, die Knoten einfärbt, sie in Postorder auf einen Stack legt und bei der Erkennung eines Zyklus False zurückgibt. Nachdem alle Knoten besucht wurden, ergibt der umgekehrte Stack die topologische Reihenfolge.
from collections import defaultdict
def dfs_topological_sort(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
stack = []
def dfs(node):
color[node] = GREY
for nxt in graph[node]:
if color[nxt] == GREY:
return False # cycle
if color[nxt] == WHITE:
if not dfs(nxt):
return False
color[node] = BLACK
stack.append(node)
return True
for i in range(n):
if color[i] == WHITE:
if not dfs(i):
return [] # cycle
return stack[::-1]
print(dfs_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Iterative DFS zur Vermeidung eines Stack-Überlaufs
Das Rekursionslimit von Python (standardmäßig 1000) kann bei großen Graphen problematisch sein. Eine iterative DFS mit einem expliziten Stack vermeidet dieses Problem. Der Trick besteht darin, zunächst (node, False) abzulegen. Beim Entfernen mit False wird (node, True) abgelegt (das bedeutet: „Ich kehre nach der Untersuchung hierher zurück“), anschließend werden alle noch unbesuchten Nachbarn mit False abgelegt. Beim Entfernen mit True wird der Knoten BLACK eingefärbt und auf den Ergebnis-Stack gelegt.
from collections import defaultdict
def dfs_topo_iterative(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
WHITE, GREY, BLACK = 0, 1, 2
color = [WHITE] * n
result = []
for start in range(n):
if color[start] != WHITE:
continue
stack = [(start, False)]
while stack:
node, returning = stack.pop()
if returning:
color[node] = BLACK
result.append(node)
elif color[node] == WHITE:
color[node] = GREY
stack.append((node, True)) # will return here
for nxt in graph[node]:
if color[nxt] == WHITE:
stack.append((nxt, False))
return result[::-1]DFS und Kahn im Vergleich
Beide Verfahren laufen in O(V + E). Die wichtigsten Unterschiede: Kahn (BFS) erzeugt auf natürliche Weise eine Reihenfolge, in der die frühesten Abhängigkeiten zuerst erscheinen, und bietet eine einfachere Zykluserkennung (Längenvergleich). DFS in Postorder arbeitet rekursiv und erkennt Rückkanten explizit. Kahn wird bevorzugt, wenn das Ergebnis ohne Umkehrung in der Vorwärtsreihenfolge benötigt wird. DFS wird bevorzugt, wenn Sie die vollständige Postorder für andere Zwecke benötigen (z. B. zur Erkennung von SCCs). Beide Ansätze sind in Vorstellungsgesprächen akzeptabel.
Postorder bei einem Baum und einem DAG
In einem Baum besucht die Postorder den linken Teilbaum → den rechten Teilbaum → die Wurzel. In einem DAG besucht die Postorder-DFS alle Abhängigkeiten eines Knotens, bevor sie den Knoten selbst verarbeitet — dieselbe Idee, verallgemeinert auf mehrere Vorgänger und beliebige Graphstrukturen. Die Wurzel eines DFS-Baums (der Startknoten) wird unter seinen Nachfolgern zuletzt auf den Stack gelegt und erscheint dadurch im umgekehrten Stack an erster Stelle — die korrekte topologische Position für einen Knoten ohne Vorgänger.
Alien Dictionary (LeetCode 269)
Alien Dictionary: Gegeben ist eine sortierte Liste von Wörtern in einer fremden Sprache. Leiten Sie daraus die Reihenfolge der Zeichen ab. Vergleichen Sie benachbarte Wörter Zeichen für Zeichen, um den ersten Unterschied zu finden — daraus ergibt sich eine Kante c1 → c2, die bedeutet, dass c1 vor c2 kommt. Sammeln Sie alle solchen Kanten und führen Sie eine topologische Sortierung durch, um die Reihenfolge der fremden Zeichen zu bestimmen. Wenn ein Zyklus existiert, ist die Reihenfolge ungültig.
from collections import defaultdict
def alienOrder(words):
graph = defaultdict(set)
all_chars = set(c for w in words for c in w)
for i in range(len(words)-1):
w1, w2 = words[i], words[i+1]
if len(w1) > len(w2) and w1.startswith(w2):
return '' # invalid (prefix comes after)
for c1, c2 in zip(w1, w2):
if c1 != c2:
graph[c1].add(c2)
break
# DFS topological sort on character graph
WHITE, GREY, BLACK = 0, 1, 2
color = {c: WHITE for c in all_chars}
result = []
def dfs(c):
color[c] = GREY
for nxt in graph[c]:
if color[nxt] == GREY: return False
if color[nxt] == WHITE and not dfs(nxt): return False
color[c] = BLACK
result.append(c)
return True
for c in all_chars:
if color[c] == WHITE:
if not dfs(c): return ''
return ''.join(result[::-1])
print(alienOrder(['wrt','wrf','er','ett','rftt'])) # 'wertf'Topologische Sortierung mit Einschränkungen
Bei einigen Aufgaben soll eine topologische Sortierung zusätzliche Einschränkungen erfüllen, beispielsweise die relative Reihenfolge von Elementen aus der ursprünglichen Liste beibehalten. Kombinieren Sie Kahns Algorithmus mit einer benutzerdefinierten Priority Queue oder einer Vorsortierung: Bewahren Sie die ursprüngliche relative Reihenfolge, indem Sie den Inhalt der Queue bei jedem Schritt stabil sortieren. Diese Varianten mit Einschränkungen prüfen, ob Sie die Flexibilität des Algorithmus umfassender verstanden haben.
Topologische Sortierungsprobleme erkennen
Typische Formulierungen in Aufgaben aus Vorstellungsgesprächen, die auf eine topologische Sortierung hindeuten, sind: „gegebene Abhängigkeiten“, „Voraussetzungen“, „Reihenfolge von Aufgaben“, „Build-Reihenfolge“, „können alle Aufgaben abgeschlossen werden?“, „finden Sie eine gültige Reihenfolge“. Wenn die Aufgabe eine Reihenfolge von Elementen betrifft, bei der einige vor anderen kommen müssen, erstellen Sie einen gerichteten Graphen und wenden Sie Kahns oder eine DFS-basierte topologische Sortierung an. Die Zykluserkennung ist in derselben Aufgabe häufig eine zusätzliche Anforderung.
Ausgaben von DFS und Kahn vergleichen
DFS und Kahn können für denselben Graphen unterschiedliche gültige topologische Reihenfolgen erzeugen. Beide sind korrekt — ein DAG kann mehrere gültige topologische Reihenfolgen besitzen. Um die Korrektheit zu überprüfen, stellen Sie für jede Kante u → v im Graphen sicher, dass u in der Ausgabereihenfolge vor v steht. Wenn eine Aufgabe eine bestimmte Reihenfolge verlangt (z. B. die lexikografisch kleinste), verwenden Sie Kahn mit einem Min-Heap — die Postorder von DFS erzeugt die lexikografisch kleinste Reihenfolge nicht auf natürliche Weise.
Kurze Überprüfung
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Die topologische Sortierung mit DFS in Postorder legt Knoten ab, nachdem alle ihre Abhängigkeiten untersucht wurden, die Dreifarbmarkierung (WHITE/GREY/BLACK) erkennt Zyklen anhand von Rückkanten zu GREY-Knoten und das Umkehren des Postorder-Stacks ergibt eine gültige topologische Reihenfolge. Als Nächstes wenden wir die topologische Sortierung direkt auf die Probleme Course Schedule I und II an.
Häufig gestellte Fragen
Ist die Lektion „Topologische Sortierung per DFS-Postorder“ kostenlos?
Ja — der vollständige Text von „Topologische Sortierung per DFS-Postorder“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Topologische Sortierung per DFS-Postorder“?
Führen Sie DFS aus und legen Sie jeden Knoten auf einen Stack, nachdem seine Nachbarn vollständig erkundet wurden. Entnehmen Sie anschließend die Knoten vom Stack, um eine gültige topologische Reihen… Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Topologische Sortierung per DFS-Postorder“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Kahns Algorithmus: Topologische Sortierung mit BFS
- Topologische Sortierung per DFS-Postorder
- Course Schedule I und II
- Stark zusammenhängende Komponenten mit Kosaraju