Topologisk sortering med DFS-efterorden
Kør DFS, og læg hver node på en stak, når alle dens naboer er færdigbehandlet; tag derefter noderne af stakken for at få en gyldig topologisk rækkefølge.
Topologisk sortering med DFS-efterorden er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Idéen bag topologisk sortering med DFS
Den anden klassiske algoritme til topologisk sortering bruger DFS med post-order-behandling. Når alle naboerne til en knude (og deres efterkommere) er udforsket fuldstændigt, lægges knuden på en stak. Når alle knuder er behandlet, tages knuderne af stakken for at aflæse den topologiske rækkefølge. En knude, der lægges på stakken efter alle dens afhængigheder, skal stå først i rækkefølgen — derfor er den omvendte post-order-rækkefølge den topologiske sortering.
Intuitionen bag post-order
Forestil dig en afhængighedsgraf, hvor kursus A kræver kursus B. Når DFS besøger A, kaldes DFS først rekursivt på B. B har ingen forudsætninger, så det afsluttes først og lægges først på stakken. Derefter afsluttes A og lægges på stakken. Når elementerne tages af stakken, kommer A før B i resultatet — men til sidst vender vi rækkefølgen om, så B kommer før A: tag først B og derefter A. Post-order lægger afhængigheder på stakken før de elementer, der afhænger af dem, så den omvendte stak er en gyldig topologisk rækkefølge.
DFS med tre farver til cyklusdetektion
Brug tre tilstande for besøgte knuder: WHITE (0) = ikke besøgt, GREY (1) = behandles i øjeblikket (i DFS-kaldstakken), BLACK (2) = fuldstændigt behandlet. En tilbagekant — en kant til en GREY-knude — angiver en cyklus. Kanter til BLACK-knuder er sikre (de er allerede udforsket fuldstændigt). Denne trefarveordning registrerer korrekt alle cyklusser i rettede 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)Komplet implementering af topologisk sortering med DFS
Brug en rekursiv DFS, der farvelægger knuder, lægger dem på en stak i post-order og returnerer False, hvis der registreres en cyklus. Når alle knuder er besøgt, giver stakken i omvendt rækkefølge den topologiske rækkefølge.
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 for at undgå stack overflow
Pythons rekursionsgrænse (som standard 1000) kan give problemer i store grafer. En iterativ DFS med en eksplicit stak undgår dette. Tricket er først at lægge (node, False) på stakken; når elementet tages af stakken med False, lægges (node, True) på (hvilket betyder »jeg vender tilbage hertil efter udforskningen«), og alle ubesøgte naboer lægges på med False. Når elementet tages af stakken med True, farvelægges det BLACK og lægges på resultatstakken.
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: sammenligning
Begge kører i O(V + E). De vigtigste forskelle er: Kahns algoritme (BFS) producerer naturligt knuder i en rækkefølge, hvor de tidligste afhængigheder kommer først, og har en enklere cyklusdetektion (kontrol af længden). DFS med post-order fungerer rekursivt og registrerer eksplicit tilbagekanter. Kahn foretrækkes, når du vil have resultatet i fremadgående rækkefølge uden at vende det om. DFS foretrækkes, når du har brug for den fulde post-order-rækkefølge til andre formål (f.eks. detektion af SCC'er). Begge metoder er acceptable til interviews.
Post-order på et træ versus en DAG
I et træ besøger post-order det venstre undertræ → det højre undertræ → roden. I en DAG besøger post-order-DFS alle afhængigheder af en knude, før selve knuden behandles — det er den samme idé generaliseret til flere forgængere og en vilkårlig grafstruktur. Roden i et DFS-træ (startknuden) lægges på stakken efter alle sine efterkommere, så den står først i den omvendte stak — den korrekte topologiske placering for en knude uden forgængere.
Alien Dictionary (LeetCode 269)
Alien Dictionary: Givet en sorteret liste over ord på et fremmed sprog skal du udlede rækkefølgen af tegnene. Sammenlign tilstødende ord tegn for tegn for at finde den første forskel — det giver en kant c1 → c2, hvilket betyder, at c1 kommer før c2. Indsaml alle sådanne kanter, og kør topologisk sortering for at finde rækkefølgen af tegnene i det fremmede sprog. Hvis der findes en cyklus, er rækkefølgen ugyldig.
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ænsninger
Nogle opgaver beder om en topologisk sortering, der opfylder yderligere begrænsninger, f.eks. at bevare elementernes indbyrdes rækkefølge fra den oprindelige liste. Kombinér Kahns algoritme med en tilpasset prioritetskø eller en forudgående sortering: Bevar elementernes oprindelige indbyrdes rækkefølge ved at bruge en stabil sortering af køens indhold ved hvert trin. Disse varianter med begrænsninger afprøver en dybere forståelse af algoritmens fleksibilitet.
Genkendelse af problemer med topologisk sortering
Signalord og -formuleringer i interviewopgaver, der peger på topologisk sortering, er: »givne afhængigheder«, »forudsætninger«, »opgaverækkefølge«, »byggerækkefølge«, »kan alle opgaver gennemføres?« og »find en gyldig sekvens«. Hvis opgaven handler om at ordne elementer, hvor nogle skal komme før andre, skal du opbygge en rettet graf og anvende Kahns eller DFS' topologiske sortering. Cyklusdetektion er ofte et yderligere krav i den samme opgave.
Sammenligning af resultater fra DFS og Kahn
DFS og Kahn kan producere forskellige gyldige topologiske rækkefølger for den samme graf. Begge er korrekte — en DAG kan have flere gyldige topologiske rækkefølger. Kontrollér korrektheden ved at tjekke, at u for hver kant u → v i grafen står før v i resultatets rækkefølge. Hvis en interviewopgave kræver en bestemt rækkefølge (f.eks. den leksikografisk mindste), skal du bruge Kahn med en min-heap — DFS med post-order producerer ikke naturligt den leksikografisk mindste rækkefølge.
Hurtigt tjek
Afprøv din forståelse af begreberne fra denne lektion i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion har du lært: DFS-baseret topologisk sortering med post-order lægger knuder på stakken, efter at alle deres afhængigheder er udforsket, markering med tre farver (WHITE/GREY/BLACK) registrerer cyklusser via tilbagekanter til GREY-knuder, og at vende post-order-stakken om giver en gyldig topologisk rækkefølge. Næste gang anvender vi topologisk sortering direkte på Course Schedule-problemerne I og II.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Topologisk sortering med DFS-efterorden” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Topologisk sortering med DFS-efterorden”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Topologisk sortering med DFS-efterorden”?
Kør DFS, og læg hver node på en stak, når alle dens naboer er færdigbehandlet; tag derefter noderne af stakken for at få en gyldig topologisk rækkefølge. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Topologisk sortering med DFS-efterorden”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Kahns algoritme: Topologisk sortering med BFS
- Topologisk sortering med DFS-efterorden
- Course Schedule I og II
- Stærkt sammenhængende komponenter med Kosaraju