Topologisch sorteren met DFS in post-order
Voer DFS uit en plaats elke knoop op een stack nadat alle buren volledig zijn verkend; haal daarna de stack leeg voor een geldige topologische volgorde.
Topologisch sorteren met DFS in post-order is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 2 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Idee voor topologische sortering op basis van DFS
Het tweede klassieke algoritme voor topologische sortering gebruikt DFS met postorderverwerking. Nadat alle buren van een knoop en hun nakomelingen volledig zijn verkend, plaats je de knoop op een stapel. Wanneer alle knopen zijn verwerkt, haal je de knopen van de stapel om de topologische volgorde te lezen. Een knoop die pas na al zijn afhankelijkheden op de stapel wordt geplaatst, komt juist als eerste in de volgorde. De omgekeerde postorder is dus de topologische sortering.
De intuïtie achter postorder
Stel je een afhankelijkheidsgraaf voor waarin cursus A cursus B vereist. Wanneer DFS A bezoekt, gaat de functie eerst recursief naar B. B heeft geen vereisten, dus B wordt als eerste voltooid en als eerste op de stapel geplaatst. Daarna wordt A voltooid en op de stapel geplaatst. Als je de stapel uitleest, krijg je A vóór B in de uitvoer. We draaien de volgorde echter aan het einde om, waardoor B vóór A komt te staan: neem eerst B en daarna A. Postorder plaatst afhankelijkheden vóór de knopen die ervan afhangen, dus de omgekeerde stapel vormt een geldige topologische volgorde.
DFS met drie kleuren voor cyclusdetectie
Gebruik drie statussen voor bezochte knopen: WHITE (0) = niet bezocht, GREY (1) = momenteel in verwerking (in de aanroepstapel van DFS), BLACK (2) = volledig verwerkt. Een terugrand — een kant naar een GREY-knoop — wijst op een cyclus. Kanten naar BLACK-knopen zijn veilig, omdat die al volledig zijn verkend. Dit schema met drie kleuren detecteert alle cycli in gerichte grafen correct.
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)Volledige implementatie van topologische sortering met DFS
Gebruik een recursieve DFS die knopen kleurt, ze in postorder op een stapel plaatst en bij het detecteren van een cyclus False retourneert. Nadat alle knopen zijn bezocht, geeft de omgekeerde stapel de topologische volgorde.
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)]))Iteratieve DFS om stapeloverloop te voorkomen
De recursielimiet van Python (standaard 1000) kan een probleem zijn bij grote grafen. Een iteratieve DFS met een expliciete stapel voorkomt dit. De truc is om aanvankelijk (node, False) op de stapel te plaatsen. Wanneer dit paar met False wordt verwijderd, plaats je (node, True) terug (wat betekent: 'ik kom hier terug nadat ik de knoop heb verkend') en plaats je alle nog niet bezochte buren met False op de stapel. Wanneer het paar met True wordt verwijderd, kleur je de knoop BLACK en plaats je hem op de resultaatstapel.
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 versus Kahn: vergelijking
Beide algoritmen draaien in O(V + E). Belangrijke verschillen: het algoritme van Kahn (BFS) produceert vanzelf knopen in een volgorde waarin afhankelijkheden het vroegst komen en heeft eenvoudigere cyclusdetectie (controle van de lengte). DFS met postorder werkt recursief en detecteert terugkanten expliciet. Het algoritme van Kahn heeft de voorkeur wanneer je het resultaat in voorwaartse volgorde wilt zonder omkeren. DFS heeft de voorkeur wanneer je de volledige postorder nodig hebt voor andere doeleinden, zoals SCC-detectie. Beide zijn aanvaardbaar tijdens sollicitatiegesprekken.
Postorder in een boom versus een DAG
In een boom bezoekt postorder eerst de linker deelboom, daarna de rechter deelboom en vervolgens de wortel. In een DAG bezoekt DFS met postorder alle afhankelijkheden van een knoop voordat de knoop zelf wordt verwerkt. Het is hetzelfde idee, veralgemeend naar meerdere voorgangers en een willekeurige graafstructuur. De wortel van een DFS-boom (de startknoop) wordt als laatste van zijn nakomelingen op de stapel geplaatst, waardoor hij als eerste in de omgekeerde stapel verschijnt. Dat is de juiste topologische positie voor een knoop zonder voorgangers.
Alien Dictionary (LeetCode 269)
Alien Dictionary: gegeven een gesorteerde lijst woorden in een onbekende taal leid je de volgorde van de tekens af. Vergelijk aangrenzende woorden teken voor teken om het eerste verschil te vinden. Dat levert een kant c1 → c2 op, wat betekent dat c1 vóór c2 komt. Verzamel al deze kanten en voer een topologische sortering uit om de volgorde van de tekens in de onbekende taal te bepalen. Als er een cyclus bestaat, is de volgorde ongeldig.
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 sortering met beperkingen
Sommige problemen vragen om een topologische sortering die aan extra beperkingen voldoet, zoals het behouden van de relatieve volgorde van elementen uit de oorspronkelijke lijst. Combineer het algoritme van Kahn met een aangepaste prioriteitswachtrij of sorteer vooraf: behoud de oorspronkelijke relatieve volgorde door de inhoud van de wachtrij bij elke stap stabiel te sorteren. Deze varianten met beperkingen testen een dieper begrip van de flexibiliteit van het algoritme.
Topologische sorteerproblemen herkennen
Signaalzinnen in sollicitatieproblemen die wijzen op topologische sortering zijn: 'gegeven afhankelijkheden', 'vereisten', 'taakvolgorde', 'bouwvolgorde', 'kunnen alle taken worden voltooid?' en 'vind een geldige volgorde'. Als het probleem gaat over een volgorde van elementen waarbij sommige elementen vóór andere moeten komen, bouw je een gerichte graaf en pas je topologische sortering met Kahn of DFS toe. Cyclusdetectie is in hetzelfde probleem vaak een aanvullende vereiste.
Uitvoer van DFS en Kahn vergelijken
DFS en het algoritme van Kahn kunnen voor dezelfde graaf verschillende geldige topologische volgordes opleveren. Beide zijn correct: een DAG kan meerdere geldige topologische volgordes hebben. Controleer voor de juistheid dat voor elke kant u → v in de graaf u vóór v staat in de uitvoervolgorde. Gebruik voor sollicitatieproblemen die een specifieke volgorde vereisen, zoals de lexicografisch kleinste volgorde, Kahn met een minimumheap. DFS met postorder levert niet vanzelf de lexicografisch kleinste volgorde op.
Korte toets
Controleer je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep in deze les.
Samenvatting van de les
In deze les heb je geleerd dat topologische sortering met DFS-postorder knopen op de stapel plaatst nadat al hun afhankelijkheden zijn verkend, dat markering met drie kleuren (WHITE/GREY/BLACK) cycli detecteert via terugkanten naar GREY-knopen en dat het omkeren van de postorderstapel een geldige topologische volgorde oplevert. Hierna passen we topologische sortering rechtstreeks toe op Course Schedule I en II.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Topologisch sorteren met DFS in post-order” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Topologisch sorteren met DFS in post-order”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Topologisch sorteren met DFS in post-order”?
Voer DFS uit en plaats elke knoop op een stack nadat alle buren volledig zijn verkend; haal daarna de stack leeg voor een geldige topologische volgorde. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 2 van 4.
Hoe lang duurt de les “Topologisch sorteren met DFS in post-order”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Algoritme van Kahn: topologisch sorteren met BFS
- Topologisch sorteren met DFS in post-order
- Course Schedule I en II
- Sterk samenhangende componenten met Kosaraju