Topologisk sortering med DFS i postorder
Kör DFS och lägg varje nod på en stack när alla dess grannar har utforskats färdigt. Ta sedan bort noderna från stacken för att få en giltig topologisk ordning.
Topologisk sortering med DFS i postorder är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 2 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Idé för topologisk sortering baserad på DFS
Den andra klassiska algoritmen för topologisk sortering använder DFS med efterordningsbearbetning. När alla grannar till en nod (och deras efterföljare) har utforskats helt lägger du noden på en stack. När alla noder har behandlats tar du bort noder från stacken för att läsa den topologiska ordningen. En nod som läggs på stacken efter att alla dess beroenden har behandlats ska komma först i ordningen — därför är den omvända efterordningen den topologiska sorteringen.
Intuitionen bakom efterordning
Föreställ dig en beroendegraf där kurs A kräver kurs B. När DFS besöker A går den först rekursivt vidare till B. B har inga förkunskapskrav, så den blir klar först och läggs först på stacken. Sedan blir A klar och läggs på stacken. När stacken töms hamnar A före B i resultatet — men vi vänder på ordningen i slutet, vilket ger B före A: läs B först och sedan A. Efterordning lägger beroenden före det som är beroende av dem, så den omvända stacken är en giltig topologisk ordning.
DFS med tre färger för cykeldetektering
Använd tre tillstånd för besökta noder: WHITE (0) = obesökt, GREY (1) = bearbetas för närvarande (finns i DFS-anropsstacken), BLACK (2) = färdigbehandlad. En bakåtriktad kant — en kant till en GREY-nod — visar att det finns en cykel. Kanter till BLACK-noder är säkra (de har redan utforskats helt). Detta trefärgsschema upptäcker korrekt alla cykler i riktade grafer.
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)Fullständig implementation av topologisk sortering med DFS
Använd en rekursiv DFS som färglägger noder, lägger dem på en stack i efterordning och returnerar False när en cykel upptäcks. När alla noder har besökts ger stacken, läst bakifrån, den topologiska ordningen.
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)]))Iterativ DFS för att undvika stacköversvämning
Pythons rekursionsgräns (standardvärde 1000) kan vara ett problem för stora grafer. En iterativ DFS med en explicit stack undviker detta. Tricket är att först lägga (node, False) på stacken. När den tas bort med False lägger du (node, True) på stacken (vilket betyder ”jag återvänder hit efter utforskningen”) och lägger alla obesökta grannar på stacken med False. När noden tas bort med True färglägger du den BLACK och lägger den på resultatstacken.
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 jämfört med Kahn: jämförelse
Båda körs i O(V + E). Viktiga skillnader: Kahns algoritm (BFS) producerar naturligt noder i ordningen tidigaste beroende först och har enklare cykeldetektering (kontroll av längden). DFS med efterordning fungerar rekursivt och upptäcker bakåtriktade kanter uttryckligen. Kahn föredras när du vill ha resultatet i framåtriktad ordning utan att vända på det. DFS föredras när du behöver den fullständiga efterordningen för andra ändamål (till exempel detektering av SCC). Båda är acceptabla på tekniska intervjuer.
Efterordning i ett träd jämfört med en DAG
I ett träd besöker efterordningen vänster delträd → höger delträd → roten. I en DAG besöker DFS med efterordning alla beroenden till en nod innan noden själv behandlas — samma idé generaliserad till flera föregångare och godtycklig grafstruktur. Roten i ett DFS-träd (startnoden) läggs på stacken sist bland sina efterföljare, vilket gör att den hamnar först i den omvända stacken — den korrekta topologiska positionen för en nod utan föregångare.
Alien Dictionary (LeetCode 269)
Alien Dictionary: givet en sorterad lista med ord på ett främmande språk ska du härleda teckenordningen. Jämför intilliggande ord tecken för tecken för att hitta den första skillnaden — det ger en kant c1 → c2, vilket betyder att c1 kommer före c2. Samla alla sådana kanter och kör topologisk sortering för att skapa ordningen för de främmande tecknen. Om det finns en cykel är ordningen ogiltig.
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'Topologisk sortering med begränsningar
Vissa problem kräver en topologisk sortering som uppfyller ytterligare begränsningar, till exempel att den relativa ordningen för element från originallistan bevaras. Kombinera Kahns algoritm med en anpassad prioritetskö eller försortering: behåll elementens ursprungliga relativa ordning genom att använda en stabil sortering av köinnehållet i varje steg. Dessa begränsade varianter testar en djupare förståelse av algoritmens flexibilitet.
Att känna igen problem med topologisk sortering
Formuleringar i intervjuproblem som ofta signalerar topologisk sortering är: ”given dependencies”, ”prerequisites”, ”task ordering”, ”build order”, ”can all tasks be completed?”, ”find a valid sequence”. Om problemet handlar om att ordna element där vissa måste komma före andra bygger du en riktad graf och använder Kahns algoritm eller topologisk sortering med DFS. Cykeldetektering är ofta ett ytterligare krav i samma problem.
Jämförelse av resultat från DFS och Kahn
DFS och Kahn kan producera olika giltiga topologiska ordningar för samma graf. Båda är korrekta — en DAG kan ha flera giltiga topologiska ordningar. Kontrollera att u → v för varje kant i grafen innebär att u kommer före v i resultatordningen. För intervjuproblem som kräver en specifik ordning (till exempel den lexikografiskt minsta) använder du Kahn med en min-heap — DFS med efterordning producerar inte naturligt den lexikografiskt minsta ordningen.
Snabbkontroll
Testa dina kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen har du lärt dig att topologisk sortering med DFS och efterordning lägger noder på stacken efter att alla deras beroenden har utforskats, att markering med tre färger (WHITE/GREY/BLACK) upptäcker cykler via bakåtriktade kanter till GREY-noder och att den omvända efterordningsstacken ger en giltig topologisk ordning. Nästa steg är att tillämpa topologisk sortering direkt på Course Schedule-problemen I och II.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Topologisk sortering med DFS i postorder” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Topologisk sortering med DFS i postorder”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Topologisk sortering med DFS i postorder”?
Kör DFS och lägg varje nod på en stack när alla dess grannar har utforskats färdigt. Ta sedan bort noderna från stacken för att få en giltig topologisk ordning. Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”Topologisk sortering med DFS i postorder”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Kahns algoritm: topologisk sortering med BFS
- Topologisk sortering med DFS i postorder
- Course Schedule I och II
- Starkt sammanhängande komponenter med Kosaraju