Topologisk sortering med Kahns algoritme
Ordn opgaver, der afhænger af andre
Topologisk sortering med Kahns algoritme er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad en topologisk rækkefølge er
En topologisk rækkefølge lister alle knuder i en rettet graf, så hver kant går fra en tidligere til en senere knude. Tænk på opgaver, der skal udføres før de opgaver, som afhænger af dem.
Kun DAG'er er tilladt
Dette fungerer kun på en DAG, altså en rettet acyklisk graf. Hvis der findes en cyklus, kan ingen gyldig rækkefølge opfylde alle afhængigheder.
Idéen med indgrader
Kahns algoritme bygger på indgraden: hvor mange kanter der peger ind på en knude. En knude med indgrad nul har ingen uopfyldte afhængigheder.
Tæl hver indgrad
Første gennemløb: gå alle kanter igennem, og tæl hvor mange gange hver knude er destination. Så får du hver knudes indgrad.
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1Fyld køen med klar knuder
Alle knuder med indgrad nul er klar med det samme, så læg dem alle i en kø for at starte.
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)Behandl én knude
Tag en klar knude ud af køen, og tilføj den til din rækkefølge. Den er sikker nu, fordi intet, der stadig mangler at blive behandlet, afhænger af den.
u = q.popleft()
order.append(u)Frigiv dens naboer
For hver nabo skal du mindske indgraden med én. Når en nabo når nul, er den klar og kommer i køen.
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)Gentag, indtil køen er tom
Bliv ved med at tage knuder ud og frigive naboer, indtil køen er tom. Rækkefølgen vokser med én sikker knude ad gangen, indtil alle knuder er placeret.
Find en cyklus uden ekstra arbejde
Hvis din endelige rækkefølge indeholder færre end n knuder, har en cyklus holdt resten tilbage. Kahns algoritme giver dig cyklusdetektion uden ekstra omkostninger.
if len(order) < n:
print('cycle exists')Køretiden
Hver knude og kant besøges én gang, så Kahns algoritme kører i O(V + E). Det skalerer til grafer med millioner af kanter.
Mange gyldige rækkefølger
Når flere knuder er klar på samme tid, kan en hvilken som helst af dem komme først. Derfor har en DAG ofte mange gyldige topologiske rækkefølger og ikke kun én.
Hurtigt tjek
Du er færdig med Kahns algoritme, men rækkefølgen indeholder færre end n knuder. Hvad betyder det?
Opsummering: Kahns algoritme
Tæl indgraderne, læg nullerne i køen, tag en knude ud, formindsk naboernes indgrader, og gentag. Det er en enkel topologisk sortering i O(V+E). 🚀
Lær Forberedelse til kodeinterviews 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
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Topologisk sortering med Kahns algoritme” gratis?
Ja — hele teksten til “Topologisk sortering med Kahns algoritme” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Topologisk sortering med Kahns algoritme”?
Ordn opgaver, der afhænger af andre Du øver dig i Forberedelse til kodeinterviews 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å Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews 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 1 af 4.
Hvor lang tid tager lektionen “Topologisk sortering med Kahns algoritme”?
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 Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-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
- Topologisk sortering med Kahns algoritme
- Find cyklusser i rettede grafer
- Stærkt sammenhængende komponenter
- Broer og artikulationspunkter