Kahns algoritme: Topologisk sortering med BFS
Beregn inngrader for alle noder, legg noder med inngrad null i en kø, og behandle køen for å lage en topologisk rekkefølge samtidig som sykler oppdages.
Kahns algoritme: Topologisk sortering med BFS er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva er topologisk sortering?
En topologisk sortering av en rettet asyklisk graf (DAG) er en rekkefølge på nodene der hver rettet kant u → v innebærer at u kommer før v i rekkefølgen. Den representerer en gyldig utførelsesrekkefølge for oppgaver med avhengigheter – som byggesystemer, emneplanlegging eller pakkehåndtering. Bare DAG-er har gyldige topologiske sorteringer; en syklus gjør det umulig.
Kahns algoritme: Grunntanken
Kahns algoritme er en BFS-basert tilnærming til topologisk sortering. Hovedinnsikten er at en node med inngrad 0 (ingen forutsetninger) kan plasseres først i rekkefølgen. Etter at den er plassert, fjernes den, og inngraden til naboene reduseres. Nye noder med inngrad 0 blir tilgjengelige. Gjenta dette til alle noder er plassert, eller til en syklus oppdages (noder har fortsatt inngrad større enn 0).
Beregning av inngrad
Bygg først en naboliste og beregn inngraden (antallet innkommende kanter) for hver node. Noder med inngrad 0 er startpunktene – de har ingen avhengigheter. For en graf med kantene [(0,1),(0,2),(1,3),(2,3)] er inngradene: 0→0, 1→1, 2→1, 3→2. Bare node 0 starter med inngrad 0.
from collections import deque, defaultdict
def compute_in_degree(n, edges):
in_degree = [0] * n
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
return graph, in_degree
graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind) # [0, 1, 1, 2]Implementering av Kahns algoritme
Legg alle noder med inngrad 0 i en kø. Behandle hver node: legg den til i resultatet, reduser deretter inngraden til hver nabo, og legg naboen i køen hvis inngraden blir 0. Hvis resultatlisten inneholder færre noder enn grafen, finnes det en syklus – noen noder kunne aldri tas ut av køen.
from collections import deque, defaultdict
def kahn_topological_sort(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
if len(order) == n:
return order # valid topological sort
return [] # cycle detected
print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))Syklusdeteksjon med Kahn
Kahns algoritme gir gratis syklusdeteksjon: hvis len(order) < n, ble noen noder aldri lagt i køen fordi inngraden deres aldri ble 0 – de er del av en syklus. Dette er ryddigere enn å vedlikeholde en fargekodet tabell over besøkte noder. Returner en tom liste for å signalisere at det finnes en syklus.
# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result) # [] (cycle detected)
# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result) # [0, 1, 2]Tids- og plasskompleksitet
Kahns algoritme behandler hver node én gang (tas ut av køen én gang) og hver kant én gang (inngraden reduseres én gang). Tidskompleksiteten er O(V + E). Plasskompleksiteten er O(V + E) for nabolisten og inngradstabellen, pluss O(V) for køen. Dette er optimalt – som et minimum må alle noder og kanter leses for å produsere en gyldig rekkefølge.
Leksikografisk minste topologiske sortering
Kahns algoritme med en min-heap i stedet for en kø produserer den leksikografisk minste topologiske sorteringen. Bytt ut deque med heapq: legg inn (node), og behandle alltid den minste tilgjengelige noden først. Dette garanterer den leksikografisk minste gyldige rekkefølgen blant alle mulige topologiske sorteringer.
import heapq
from collections import defaultdict
def kahn_lex_order(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
heap = [i for i in range(n) if in_degree[i] == 0]
heapq.heapify(heap)
order = []
while heap:
node = heapq.heappop(heap)
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
heapq.heappush(heap, nxt)
return order if len(order) == n else []
print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))Anvendelse: Course Schedule I
Course Schedule (LeetCode 207): Gitt n kurs og forkunnskaper, kan alle kursene fullføres? Modeller forkunnskapene som rettede kanter, og kontroller om det finnes en gyldig topologisk sortering (det vil si ingen syklus). Returner True hvis Kahns algoritme produserer en rekkefølge med lengde n, og False hvis en syklus oppdages.
from collections import deque, defaultdict
def canFinish(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites: # b must be taken before a
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
count = 0
while queue:
node = queue.popleft()
count += 1
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return count == numCourses
print(canFinish(2, [[1,0]])) # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)Anvendelse: Course Schedule II
Course Schedule II (LeetCode 210): Returner den faktiske rekkefølgen kursene skal tas i. Det er samme fremgangsmåte som ovenfor, men returner order-listen i stedet for en boolsk verdi. Hvis det finnes en syklus, returner en tom liste. Her brukes resultatet fra Kahn direkte som svaret.
from collections import deque, defaultdict
def findOrder(numCourses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * numCourses
for a, b in prerequisites:
graph[b].append(a)
in_degree[a] += 1
queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []
print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))Parallell oppgaveplanlegging
En mer avansert anvendelse er å finne det minste antallet «runder» som trengs når oppgaver uten avhengigheter kan kjøres parallelt. Behandle Kahn nivå for nivå (på samme måte som BFS nivå for nivå): legg alle noder med inngrad 0 i køen, behandle hele den gjeldende køen som én runde, og legg deretter noder som nylig er frigjort, i køen som neste runde. Tell rundene.
from collections import deque, defaultdict
def min_rounds(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
queue = deque(i for i in range(n) if in_degree[i] == 0)
rounds = 0
while queue:
rounds += 1
for _ in range(len(queue)): # process current level
node = queue.popleft()
for nxt in graph[node]:
in_degree[nxt] -= 1
if in_degree[nxt] == 0:
queue.append(nxt)
return rounds
print(min_rounds(4, [(0,2),(1,2),(2,3)])) # 3Topologisk sortering og DP på DAG-er
Topologisk sortering muliggjør dynamisk programmering på DAG-er: behandle nodene i topologisk rekkefølge, slik at alle forgjengernes dp[u]-verdier allerede er endelige når dp[v] beregnes. Dette kombinerer topologisk sortering med DP for problemer som lengste sti i en DAG, minste kostnad for å nå alle noder eller maksimal gevinst fra en avhengighetskjede. Rekkefølgen garanterer at hver nodes DP-verdi beregnes nøyaktig én gang, etter at alle avhengighetene er behandlet.
from collections import deque, defaultdict
def longest_path_dag(V, edges):
graph = defaultdict(list)
in_degree = [0] * V
for u, v, w in edges:
graph[u].append((v, w))
in_degree[v] += 1
queue = deque(i for i in range(V) if in_degree[i] == 0)
dp = [0] * V
while queue:
u = queue.popleft()
for v, w in graph[u]:
dp[v] = max(dp[v], dp[u] + w)
in_degree[v] -= 1
if in_degree[v] == 0: queue.append(v)
return max(dp)
print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)])) # 7Hurtigsjekk
Test Deres forståelse av begrepene Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: Kahns algoritme beregner en topologisk sortering ved å fjerne noder med inngrad 0 iterativt ved hjelp av BFS, syklusdeteksjon er gratis – hvis len(order) < n, finnes det en syklus, og når køen erstattes med en min-heap, får man den leksikografisk minste topologiske sorteringen. Neste tema er en utforskning av DFS-basert topologisk sortering i etterrekkefølge som et alternativ til Kahn.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Kahns algoritme: Topologisk sortering med BFS» gratis?
Ja – hele teksten i «Kahns algoritme: Topologisk sortering med BFS» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Kahns algoritme: Topologisk sortering med BFS»?
Beregn inngrader for alle noder, legg noder med inngrad null i en kø, og behandle køen for å lage en topologisk rekkefølge samtidig som sykler oppdages. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Kahns algoritme: Topologisk sortering med BFS»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Kahns algoritme: Topologisk sortering med BFS
- Topologisk sortering med DFS-etterrekkefølge
- Course Schedule I og II
- Sterkt sammenhengende komponenter med Kosaraju